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

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
Its Kadane’s max sum subarray problem. The algorithm basically scans the input array from left to right and calculates sum of the current subarray upto current position. If current sum is less than 0 then reset the sum to zero and thus starting a new subarray. While doing this it keeps the max sum. If current sum exceeds the max sum then we reset max sum to this sum and set the max sum subarray boundary. This is an O(n) solution.

For example: A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=6 with the maxsum subarray [4, -1, 2, 1]. Below is the implementation of Kadane’s algorithm to find max sum contagious subarray:

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;
}

Now 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;
}

Maximum Product Subarray
How do we find maximum product subarray? We can similarly use Kadane’s algorithm to find maximum product subarray. But this problem has slight tricky parts. 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;
}

There can be many applications of Kadane’s algorithm in local maxima/minima optimization problems. One such problem , for example, as defined –

Given an integer N, find maximum number of set bits after flipping a single contagious segment of bits (bits from L to R index).

Constraints: 
1 <= N <= 2^100000
0 <= L <= R < log(N)

Sample Input: 146
Sample Output: 6 

Explanation: N=146 can be represented in binary as 1 0 0 1 0 0 1 0

We can get a maximum of 6 ones in the given binary array by performing the following single segment bit flip operation:
Flip [1, 5] ==> 1 1 1 0 1 1 1 0

How to solve it most efficiently? We can transform the problem of finding contagious segment of flipped bits (to maximize number of total set bits) into the problem of finding minimum sum subarray of the bits as an array. We can use Kadane’s algorithm to find largest contiguous sub array for which difference ‘numberOfZeros – numberOfOnes’ is the biggest to maximize the sum of ones after flipping zeros.

Below is implementation of the above idea which runs un O(n) time. It converts 0 to -1 and computes the sum till the sum is <=0 (there is more 0s then 1s). If the sum is > 0 starts from the beginning. The major difference compare to ordinary Kadane’s algorithm is that we are computing minima sum instead of maxima.

public static int maxSetBitsSingleSegmentFlipped(int n){
	ArrayList<Integer> bits = new ArrayList<Integer>();
	while(n > 0){
		bits.add(0, n%2);
		n = n/2;
	}
	
	//kadanes algorithm
	int localMinima = 0;
	int globalMinima = 0;
	int zeroCount = 0;
	int localOnesToFlip = 0;
	int globalOnesToFlip = 0;
	int localStart = 0;
	int globalStart = 0;
	int end = 0;
	int totalOnes = 0;
	
	for(int i = 0; i< bits.size(); i++){
		if(bits.get(i) == 0){
			localMinima += -1;
			zeroCount++;
		}
		else{
			localMinima += 1;
			localOnesToFlip++;
			totalOnes++;
		}
		
		if(localMinima < globalMinima){
			globalMinima = localMinima;
			globalStart = localStart;
			end = i;
			globalOnesToFlip = localOnesToFlip;
		}
		else if(localMinima > 0){
			localMinima = 0;
			localStart = i+1;
			localOnesToFlip = 0;
		}
	}
	
	return zeroCount > 0 ? (end - globalStart +1) - globalOnesToFlip + totalOnes - globalOnesToFlip : totalOnes;
}