/**
* 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
