package com.interview.dynamic;

/**
 * http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-
 * adjacent/
 */
public class MaxSumForNonAdjacentElements {

	/**
	 * Fast DP solution.
	 */
    public int maxSum(int arr[]) {
        int excl = 0;
        int incl = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int temp = incl;
            incl = Math.max(excl + arr[i], incl);
            excl = temp;
        }
        return incl;
    }
    
    /**
     * Recursive slow solution.
     */
	public int maxSum(int arr[], int index) {
		if (index == 0) {
			return arr[0];
		} else if (index == 1) {
			return Math.max(arr[0], arr[1]);
		}
		return Math.max(this.maxSum(arr, index - 2) + arr[index], this.maxSum(arr, index - 1));
	}    	
   
    public static void main(String args[]) {
        MaxSumForNonAdjacentElements msn = new MaxSumForNonAdjacentElements();
        int arr[] = { 2, 10, 13, 4, 2, 15, 10 };
        System.out.println(msn.maxSum(arr));
        System.out.println(msn.maxSum(arr, arr.length-1));
                
    }
}

@@ -36,91 +36,384 @@
 %0A * 
-http://www.geeksforgeeks.org/
+Date 11/03/2016%0A * @author Tushar Roy%0A *%0A * Find maximum sum for non adjacent elements.%0A * Variation is finding 
 maximum
--sum-such-that-no-two-elements-are-%0A * adjacent
+ sum non adjacent elements assuming its a circular array.%0A * So first element cannot be with last element.%0A *%0A * Time complexity O(n)%0A * Space complexity O(1)%0A *%0A * https://leetcode.com/problems/house-robber/%0A * https://leetcode.com/problems/house-robber-ii
 /%0A *
@@ -463,14 +463,20 @@
  %7B%0A%0A
-%09/**%0A%09
+    /**%0A    
  * F
@@ -492,17 +492,20 @@
 lution.%0A
-%09
+    
  */%0A    
@@ -772,21 +772,17 @@
 ;%0A    %7D%0A
-    
 %0A
+
     /**%0A
@@ -821,17 +821,20 @@
      */%0A
-%09
+    
 public i
@@ -867,18 +867,24 @@
 ndex) %7B%0A
-%09%09
+        
 if (inde
@@ -889,27 +889,36 @@
 dex == 0) %7B%0A
-%09%09%09
+            
 return arr%5B0
@@ -920,18 +920,24 @@
 arr%5B0%5D;%0A
-%09%09
+        
 %7D else i
@@ -957,11 +957,20 @@
 ) %7B%0A
-%09%09%09
+            
 retu
@@ -1002,14 +1002,26 @@
 %5D);%0A
-%09%09%7D%0A%09%09
+        %7D%0A        
 retu
@@ -1108,19 +1108,1002 @@
 ));%0A
-%09%7D    %09%0A   
+    %7D%0A%0A    /**%0A     * Find maximum sum from left to right ignoring first element.%0A     * Find maximum sum from right to left ignoring last element.%0A     * Maximum of two will be the answer. It gurantees that both first and last element%0A     * will be not selected together.%0A     */%0A    public int maxSumCircularArray(int%5B%5D nums) %7B%0A        if (nums.length == 0) %7B%0A            return 0;%0A        %7D%0A        if (nums.length == 1) %7B%0A            return nums%5B0%5D;%0A        %7D%0A        int with = nums%5B1%5D;%0A        int without = 0;%0A        for (int i = 2; i %3C nums.length; i++) %7B%0A            int newWith = without + nums%5Bi%5D;%0A            without = with;%0A            with = Math.max(with, newWith);%0A        %7D%0A%0A        int with1 = nums%5Bnums.length - 2%5D;%0A        int without1 = 0;%0A        for (int i = nums.length - 3; i %3E= 0; i--) %7B%0A            int newWith1 = without1 + nums%5Bi%5D;%0A            without1 = with1;%0A            with1 = Math.max(with1, newWith1);%0A        %7D%0A        return Math.max(with, with1);%0A    %7D%0A
 %0A   
@@ -2380,24 +2380,8 @@
 ));%0A
-                
 %0A   

Update max sum non adjacent