public class NonadjacentMaxSum {
/**
* @param args
*/
public static void main(String[] args) {
int arr[] = { 3,2,5,10,7}; // ans - 15
// int arr[] = { 3,2,5,10}; ans -13
// int arr[] = { 4,3, 13,2, 5,7,20 }; ans - 42
int answer = findMaximumNonadjacentSum(arr,0,arr.length-1);
System.out.println(answer);
}
private static int findMaximumNonadjacentSum(int[] arr, int low, int high) {
if(low==high){
return arr[low];
}
if(low+1==high){
return arr[low]>arr[high] ?arr[low] : arr[high] ;
}
while(low<high)
{
int max = -1;
int curr= arr[low];
for(int i=low+2;i<=high;i++ )
{
System.out.println("curr is "+curr);
int temp = findMaximumNonadjacentSum(arr,i,high)+curr;
System.out.println("temp is"+temp);
if(max<temp)
max=temp;
}
return max;
}
return 0;
}
}
Advertisements
