MaximumSumOfSubseqNonAdjacent.java

/*
https://www.techiedelight.com/maximum-sum-of-subsequence-with-no-adjacent-elements

This problem is similar to the concept of 0/1 Knapsack Problem. Each element can be included or excluded. All elements in the subseq must be non-adjacent.
*/

//Recursion
//Include the current element and exclude the current element. Choose the max value.

publicintmaxSumOfSubseqNonAdj(intA[], intcurrIndex, intprevIndex, intn){

//we have exhausted all elements of the array
if(currIndex == n) return0;

//exclude the current element
intexc = maxSumOfSubseqNonAdj(A, currIndex+1, prevIndex, n);

intinc = 0;

//include current element only if the it is not adjacent to the prev element considered in the subseq
if(prevIndex+1 != currIndex) inc = maxSumOfSubseqNonAdj(A, currIndex+1, currIndex, n) + A[currIndex];

//return the maximum sum possible
returnMath.max(inc, exc);

}

//Bottom Up Dynamic Programming
publicintmaxSumOfSubseqNonAdj(intA[]){
intn = A.length;

if(n == 1) returnA[0];

intsum[] = newint[n];

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

for(inti = 2 ; i < n ; i++){
intexc = sum[i-1];
intinc = sum[i-2] + A[i];

sum[i] = Math.max(exc, inc);

//Usefull if both inc, exc and A[i] are negative --> choose the maximum
sum[i] = Math.max(sum[i], A[i]);
 }

returnsum[n-1];

}

//Time and Space Complexity - O(n)

//We require only two variables to compute current sum and not entire array
publicintmaxSumOfSubseqNonAdj(intA[]){
intn = A.length;

if(n == 1) returnA[0];

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

for(inti = 2 ; i < n ; i++){
intexc = prevSum;
intinc = prevPrevSum + A[i];

intcurrSum = Math.max(inc, exc);

//Usefull if both inc, exc and A[i] are negative --> choose the maximum
currSum = Math.max(currSum, A[i]);

//Update previous values
prevPrevSum = prevSum;
prevSum = currSum;
 }

returnprevSum;
}

//Time Complexity - O(n)
//Space Complexity - O(1)