You have an array of N elements and you have to find the subarray of out of this array whose sum is maximum. The condition is no two element that you chose in your subarray should be adjacent to each other in the original array. How will you do this polynomial time??
Logic is to use dp.
ReplyDeleteFor an array of size N.
max sum will be a[i]+max(i+2) or
max(i+1).
Either consider current number and take number next to adjacent, or don't consider current number and take adjacent number.
Algorithm:
max_sum(i){
if( i > N ) return 0;
return max ( a[i]+max_sum(i+2), max_sum(i+1) );
}
Code:
private int max_sum(int i) {
if(i >= array.length){
return 0;
}
if(max[i] != 0){
return max[i];
}
int include = array[i]+max_sum(i+2);
int exclude = max_sum(i+1);
if( include > exclude){
max[i]=include;
selected[i]=true;
if((i+1)<array.length)
selected[i+1]=false;
return include;
}else{
max[i]=exclude;
selected[i]=false;
return exclude;
}
}
Finally , traverse selected boolean array to print the numbers.