NonadjacentMaxSum

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

}

&nbsp;

Advertisement