Algorithm_Maximum Subarray - xwu36/LeetCode GitHub Wiki

Problem #53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

1. Kadane's algorithm

Kadane's algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position i, what is the maximum subarray sum ending at position i+1? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position i+1 includes the maximum subarray sum ending at position i as a prefix, or it doesn't. Thus, we can compute the maximum subarray sum ending at position i for all positions i by iterating once over the array. As we go, we simply keep track of the maximum sum we've ever seen.

public int maxSubArray(int[] A) {
        int maxSoFar=A[0], maxEndingHere=A[0];
        for (int i=1;i<A.length;++i){
        	maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
        	maxSoFar=Math.max(maxSoFar, maxEndingHere);	
        }
        return maxSoFar;
}

2. DP solution

public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        
        return max;
}

Problem. Max Sum of Subarray No Larger Than K

Find the contiguous subarray within an array (containing at least one number) which has the largest sum which should be at most K. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], and K = 5, the contiguous subarray [4,-1,2] has the largest sum = 5.

private int best_cumulative_sum(int ar[], int k){
	TreeSet<Integer> mySet = new TreeSet<Integer>();
	mySet.add(0);
	int best = Integer.MIN_VALUE, cum = 0;
	for(int i = 0; i < ar.length; i++){
		cum += ar[i];
		Integer key = mySet.ceiling(cum - k);
		if(key != null) best = Math.max(best, cum - key);
		mySet.add(cum);
	}
	return best;
}

Problem. Maximum sum rectangle in a 2D matrix

Given a 2D array, find the maximum sum subarray in it.

/**
* To find maxSum in 1d array
* 
* return {maxSum, left, right}
*/
public static int[] kadane(int[] a) {
        //result[0] == maxSum, result[1] == start, result[2] == end;
        int[] result = new int[]{Integer.MIN_VALUE, 0, -1};
        int currentSum = 0;
        int localStart = 0;
     
        for (int i = 0; i < a.length; i++) {
            currentSum += a[i];
            if (currentSum < 0) {
                currentSum = 0;
                localStart = i + 1;
            } else if (currentSum > result[0]) {
                result[0] = currentSum;
                result[1] = localStart;
                result[2] = i;
            }
        }
         
        //all numbers in a are negative
        if (result[2] == -1) {
            result[0] = 0;
            for (int i = 0; i < a.length; i++) {
                if (a[i] > result[0]) {
                    result[0] = a[i];
                    result[1] = i;
                    result[2] = i;
                }
            }
        }
         
        return result;
}
 
/**
* To find and print maxSum, (left, top),(right, bottom)
*/
public static void findMaxSubMatrix(int[][] a) {
        int cols = a[0].length;
        int rows = a.length;
        int[] currentResult;
        int maxSum = Integer.MIN_VALUE;
        int left = 0;
        int top = 0;
        int right = 0;
        int bottom = 0;
         
        for (int leftCol = 0; leftCol < cols; leftCol++) {
            int[] tmp = new int[rows];
     
            for (int rightCol = leftCol; rightCol < cols; rightCol++) {
         
                for (int i = 0; i < rows; i++) {
                    tmp[i] += a[i][rightCol];
                }
                currentResult = kadane(tmp);
                if (currentResult[0] > maxSum) {
                    maxSum = currentResult[0];
                    left = leftCol;
                    top = currentResult[1];
                    right = rightCol;
                    bottom = currentResult[2];
                }
            }
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️