Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

NonAdjacentMaximumSumSubsequence .java

//method 1, works only for postive numbers

public class NonAdjacentMaximumSumSubsequence {
	public static int NoAdjacentSum(int a[], int n)
	{
	   
		int[] dp =new int[n];
		dp[0] = a[0];
		dp[1] =a[1];
		dp[2] = a[2] +a[0];
		
		for(int i = 3; i<n; i++){
			dp[i] =a[i] + Math.max(dp[i-2],dp[i-3]);
			System.out.print("i is " + i + " last is "+dp[i] +" ");
			System.out.println();
		}
		System.out.println();
		System.out.println( " dp 3 is " + dp[3]);
		return dp[n-1];
		
		
	}
 
  public static void main(String[] args) {
	  int a[] = {-3,-2,4,5,-3,6};
	  int a1[] = {10,11,20,10,20};
	  int a2[] = {5,  5, 10, 40, 50, 35};
	  int a3[] = {3,2,5,10};
	  
	  int n = a.length;
	  int n1 = a1.length;
	  int n2 = a2.length;
	  int n3 = a3.length;
	   System.out.println(NoAdjacentSum(a1,n1));
  }
 
}





//method 2, works for both positive numbers and negative numbers
public class NonAdjacentMaximumSumSubsequence {
	public static int NoAdjacentSum(int a[], int n)
	{
	    int[] sum = new int[n+1];
	    sum[0] = 0;
	    sum[1] = a[0];
	    sum[2] = Math.max(a[0], a[1]);
	 
	    for (int i = 3; i <= n; i++)
	        sum[i] = Math.max(a[i-1] + sum[i-2], Math.max(sum[i-1], a[i-1]));
	 
	    return sum[n];
	}
 
  public static void main(String[] args) {
	  int a[] = {-3,-2,4,5,-3,6};
	  int a1[] = {3,2,5,10};
	  int n = a.length;
	  int n1 = a1.length;
	   System.out.println(NoAdjacentSum(a1,n1));
  }
 
}