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

Advertisements