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
You can backtrack your DP solution.
you can try record the sources when you are doing you DP
for example
and looking at the result you find out that dp[7] is the maximum value you got
so go backtracking from 7
tell me if there is any thing that you can't understand
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
opps! XDD
fixed
how will we track included elements in sequence. you added indexes but are they included elements indices only?
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?
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).
yes
and thats what i have done
by DP and backtracking
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 ?
here you are
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
try make N smaller
somtihng like 1e5
or make the array globle