maximum value of no contiguous subsequence

Given a sequence of n numbers A(1) ... A(n), give an algorithm for finding a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximum. Here the condition is we should not select two contiguous numbers.

follow up:

what if we should not select three contiguous numbers

//max subarray with no 2 contiguous

public static int maxSubWithNo2Con(int[]A){

int dp[] = new int[A.length];

dp[0]=A[0];

dp[1]=Math.max(A[0],A[1]);

for(int i =2; i < A.length;i++){

dp[i] = Math.max(A[i] + dp[i-2], dp[i-1]);

}

return dp[A.length-1];

}

//no three contiguous

public static int maxSubWithNo3Con(int[]A){

int dp[] = new int[A.length];

dp[0]=A[0];

dp[1]=Math.max(A[0]+A[1],Math.max(A[0],A[1]));

dp[2]=Math.max(A[2]+A[0], A[1]+A[0]);

for(int i = 3;i<A.length;i++){

dp[i]=Math.max(dp[i-2]+A[i], Math.max(A[i]+A[i-1]+dp[i-3],dp[i-1]));

}

return dp[dp.length-1];

}

public static void main(String[] args){

int ar[] ={1,-1,2,3,-1,-2,0,2,4,5,-2,-2,5};

System.out.println(maxSubWithNo2Con(ar));

System.out.println(maxSubWithNo3Con(ar));

}

## No comments:

Post a Comment