Friday, March 29, 2013

maximum value of no contiguous subsequence

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: