abhi55's blog

By abhi55, history, 8 days ago, In English,

My DP implementation of max sum is below but i need sequence which is giving max sum instead of max sum value.

public int maxSum(int arr[]) {
     int excl = 0;
     int incl = arr[0];
     for (int i = 1; i < arr.length; i++) {
       int temp = incl;
       incl = Math.max(excl + arr[i], incl);
       excl = temp;
     }
     return incl;
}

So 3 2 7 10 should return (3 and 10) or 3 2 5 10 7 should return (3, 5 and 7) or {5, 5, 10, 100, 10, 5} will return (5, 100 and 5) or {1, 20, 3} will return 20 i exactly want this problem solution but return value i need is sequence of elements included in max sum instead of max sum value

Update:-no need to handle -ve elements because all elements in sequence(Array) are +ve

 
 
 
 

»
8 days ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

You can backtrack your DP solution.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that will not work in case like 3 2 7 10 or 10 2 1 8 4 6 10

»
8 days ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

you can try record the sources when you are doing you DP

for example

pos :  1  2  3  4  5  6  7

arr : 10  2  1  8  4  6 10

dp  : 10  2 11 18 15 24 28

from:  0  0  1  1  3  4  4

and looking at the result you find out that dp[7] is the maximum value you got

so go backtracking from 7

now=7;

while(now!=0){

    ans.push_back(val[now]);

    now=from[now];

}

tell me if there is any thing that you can't understand

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    dp array is wrong because max value we can achieve in this test case is 28 by using sequence 10 8 10 which equals to 28 so 10 1 4 10 will be wrong sequence

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    how will we track included elements in sequence. you added indexes but are they included elements indices only?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry but I can't understand your question

      what do u mean "included elements" ,"sequence u added indexes"

      is it the backtracking step or the dp step?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        my question is that if take sequence like 3 2 7 10 i want sequence with maximum sum as output(printed) with only condition that in sequence no adjacent element taken. and in time complexity O(n).

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yes

          and thats what i have done

          by DP and backtracking

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          for the DP , hold a value MAX for the max value that you can dp from

          simultaneously , record the index of where the MAX value come from

          do you need a code for better understanding ?

»
8 days ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

here you are

#include <stdio.h>
const int N=1e6+10;
int main(){
    int n,dp[N],val[N],max,from[N],max_index;
    bool minus[N];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        if(val[i]<0){       //just don't take negative elements
            val[i]=0;
            minus[i]=true;
        }
        else minus[i]=false;
    }
    dp[1]=val[1];   // there is no elements to take before 1
    dp[2]=val[2];   //
    from[1]=0;
    from[2]=0;
    max=dp[1];
    max_index=1;
    for(int i=3;i<=n;i++){
        dp[i]=val[i]+max;
        from[i]=max_index;
        if(dp[i-1]>max){    //cause for the element i+1 ,the right most element you can take is i-1
            max=dp[i-1];
            max_index=i-1;
        }
    }
    if(dp[n]>max)max_index=n;
    while(max_index!=0){
        if(!minus[max_index])printf("%d ",val[max_index]);
        max_index=from[max_index];
    }
    printf("\n");
}
  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i compiled and run code and it is giving output 3221225725 always without taking any input value and dont handle -ve elements because elements in array are +ve

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      try make N smaller

      somtihng like 1e5

      or make the array globle

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks now it is working fine and giving correct answer for all testcases