Home » Arrays(Dont Mess With Me) » MaxSumNonConsecutive

# MaxSumNonConsecutive

/**
* Given an array of positive numbers, find the maximum sum of elements such
* that no two adjacent elements are picked
* Top down dynamic programming approach without memorisation.
* An alternate to the bottom up approach.
*/

/// i was thinking of add even , add odd, and whosoever max prints it… thats it..

```
public class MaxSumNonConsec {

public static int maxSum(int a[], int start, int end) {
int maxSum = 0;

// Trivial cases
if (start == end) {
return a[start];
} else if (start > end) {
return 0;
} else if (end - start == 1) {
return a[start] > a[end] ? a[start] : a[end];
} else if (start < 0) {
return 0;
} else if (end >= a.length) {
return 0;
}

// Subproblem solutions, DP
for (int i = start; i <= end; i++) {

int possibleMaxSub1 = maxSum(a, i + 2, end);
System.out.println("possibleMaxSub1 is "+possibleMaxSub1);

System.out.println("a[i] = "+a[i]);

int possibleMaxSub2 = maxSum(a, start, i - 2);
System.out.println("possibleMaxSub2 = "+possibleMaxSub2);

System.out.println("a[i] now is"+a[i]);

int possibleMax = possibleMaxSub1 + possibleMaxSub2 + a[i];
System.out.println("Max is "+possibleMax);

if (possibleMax > maxSum) {
maxSum = possibleMax;
}
}

return maxSum;
}

public static void main(String args[]) {
int a[] = { 3,2,5,10,7}; // 42 in this case
/// int a[] = { 4,25, 13,2, 5,7,20 }; // 50 in this case(25+5+20)

// int arr[] = { 3,2,5,10}; ans -13

System.out.println(maxSum(a, 0, a.length - 1));
}
}

```