### abhi55's blog

By abhi55, history, 11 months ago, ,

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

 » 11 months ago, # | ← Rev. 3 →   -14 You can backtrack your DP solution.
•  » » 11 months ago, # ^ |   0 that will not work in case like 3 2 7 10 or 10 2 1 8 4 6 10
 » 11 months ago, # | ← Rev. 3 →   +5 you can try record the sources when you are doing you DPfor 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 gotso 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
•  » » 11 months ago, # ^ |   +5 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
•  » » » 11 months ago, # ^ |   0 opps! XDDfixed
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 how will we track included elements in sequence. you added indexes but are they included elements indices only?
•  » » » 11 months ago, # ^ |   0 sorry but I can't understand your questionwhat do u mean "included elements" ,"sequence u added indexes"is it the backtracking step or the dp step?
•  » » » » 11 months ago, # ^ |   0 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).
•  » » » » » 11 months ago, # ^ |   0 yesand thats what i have doneby DP and backtracking
•  » » » » » 11 months ago, # ^ |   +1 for the DP , hold a value MAX for the max value that you can dp fromsimultaneously , record the index of where the MAX value come fromdo you need a code for better understanding ?
•  » » » » » » 11 months ago, # ^ |   0 yes if possible
 » 11 months ago, # | ← Rev. 3 →   +1 here you are #include 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"); } 
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 11 months ago, # ^ |   0 try make N smallersomtihng like 1e5or make the array globle
•  » » » » 11 months ago, # ^ |   0 thanks now it is working fine and giving correct answer for all testcases