/**
* 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)); } }