Max sum subsequence with non-consecutive elements - Kadane's Algorithm (DP)

Max sum subsequence with non-consecutive elements - Kadane's Algorithm (DP) - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive.

For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4].

First of all, lets solve the problem with less constraint. Suppose we need to find out max sum subarray. How we can do that efficiently?
Kadane’s Algorithm

public static int maxSumSubArray(final int[] a) {
     int maxSum = a[0];
     int maxSoFar = a[0];
     int tempBegin = 0;
     int begin = 0;
     int end = 0;

     for (int i = 1; i < a.length; i++) {
         maxSoFar += a[i];

         if (maxSoFar < 0) {
             maxSoFar = 0;
             tempBegin = i + 1;
         } else if (maxSoFar > maxSum) {
             maxSum = maxSoFar;
             begin = tempBegin;
             end = i;
         }
     }

     for (int i = begin; i <= end; i++) {
         System.out.print(a[i] + ", ");
    }
    return maxSum;
}

ow switch back to original question where we have extra constraint that the subarray elements are not consecutive. So, after understanding Kadane’s algorithm it is easy to figure out that for max sum with non-consecutive element is similar except that for each position i , we either take current element to include it to max sum that doesn’t include the previous item or not include it. We can keep two array for computing max sum including current element and excluding current element at each position. So, max sum will be max of these two at some position i. The following recurrence relation describes the logic:

max_including(i) = max{max_excluding(i-1)+a[i], a[i]}
max_excluding(i) = max{max_including(i-1), max_excluding(i-1)}
global_max = max{max_including(i), max_excluding(i)}, for each i = {0, 1, ..., n-1}

public static int maxSumSubSeqNonContagious(int a[]){
 int max_include[] = new int[a.length];
 int max_exclude[] = new int[a.length];
 max_include[0] = a[0];
 max_exclude[0] = Integer.MIN_VALUE;
 int max = a[0];
 
 for(int i = 1; i<a.length; i++){
  max_include[i] = Math.max(max_exclude[i-1]+a[i], a[i]);
  max_exclude[i] = Math.max(max_include[i-1], max_exclude[i-1]);
  max = Math.max(max_include[i], max_exclude[i]);
 }
 
 return max;
}

http://algorithmsforever.blogspot.com/2011/11/largest-non-consecutive-subsequence.html

Let sum[i] represent maximum non-consecutive subsequence sum till ith element of input[], then
sum[i] = max(sum[i-1], input[i] + sum[i-2])

which says that new sum would either be obtained by not including ith element i.e previous sum, or by including it with last to previous sum i.e input[i-2]. The new sum would be maximum of these two possibilities.

Maximum Product Subarray

http://massivealgorithms.blogspot.com/2015/08/find-number-of-bits-to-be-flipped-to.html
Maximum product can be achieved by product of positive consecutive elements and even number of consecutive negative elements. So, we just can't reset if product is negative. Instead we should keep two product - max product for positive values and min product for negative values (hence maximum contribution to product). So, at any time if we see a zero element we do reset the current run. If we see a positive element then it certainly is contributing to running product. But this positive value can also negative product more negative and hence another negative may contribute to positive product. So, we update the local negative product when we see a positive value.

If we see a negative value then it's tricky. We need to multiply this to the negative product to get a positive product. Also, the negative product now will be updated to the product of previous local maxima and the negative element.

Below is the implementation of the above idea in O(n) time. Note that, this works if there is at least one positive element in the array.

public static int maxProductSubArr(int a[]){
 int localMax = 1;
 int localMin = 1;
 int globalMaxProd = 1;
 
 for(int i = 0; i < a.length; i++){
  if(a[i] == 0){
   localMax = 1;
   localMin = 1;
  }
  else if(a[i] > 0){
   localMax *= a[i];
   localMin = Math.min(localMin*a[i],1);
  }
  else{
   int temp = localMin;
   localMin = Math.min(localMax*a[i], 1);
   localMax = Math.max(temp*a[i], 1);
  }
  
  globalMaxProd = Math.max(globalMaxProd, localMax);
 }
 
 return globalMaxProd;
}

Read full article from Max sum subsequence with non-consecutive elements - Kadane's Algorithm (DP) - Algorithms and Problem SolvingAlgorithms and Problem Solving