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.

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

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 ?

yes if possible

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

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