Problem Statement

Find the maximum subarray sum of a given array.

Approach 1:

A straight forward approach is to cacluate all subarrays for any index and find the maximum of them, if the array size is \(n\), time complexity is \(O(n^2)\).

Apprach 2 - Kadane’s Algorithm:

Kadane’s algorithm is basically a dynamic programming approach, in which we reduce the problem size and deduce the current unknows from the previous knows, or sometimes we call them states. Let’s see, if we know the maximum subarray size of array till \(i-1\), how can we deduce the maximum subarray to \(i\)? We have two options, includes \(i\) or not. If we include \(i\), we get the subarray expanded, if not, we actually start a new subarray starting from \(i\). How do we make the selction? We are finding the maximum value, so whichever is bigger, we pick it.

The above is only able to find the local maximum subarray that include \(i\), we could get the maximum of all the local maximum sum by just compare the global maximum to local every time.

    public int largestSum(int[] array) {
        int global_max = Integer.MIN_VALUE;

        int sum = 0;
        for (int num : array) {
            sum += num;
            if (sum <= num) {
            sum = num;
        }       
        global_max = Math.max(sum, global_max);
        }
        return global_max;
    }

Example

• LeetCode - 53

Simply applying the above code.

• LeetCode - 152

This is similary to maximum sum, but this time, we have to care about the minimum products, because the minimum products could become maximum if it is negtive. So we need to store both the local maximum and minimum products.

    public int maxProduct(int[] nums) {

        if (nums.length == 0) return 0;
        
        int max = nums[0], min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int prevMax = max, prevMin = min;
            max = Math.max(nums[i],Math.max(prevMax*nums[i], prevMin*nums[i]));
            min = Math.min(nums[i],Math.min(prevMax*nums[i], prevMin*nums[i]));
            
            res = Math.max(res,max);

        }
        
        return res;
    }  

• Maximum submatrix sum from a given matrix

This is an expansion of maximum subarray sum, and brings up a lot more time complexity. Since we know how to calculate maximum subarray sum, it is natural we can think how to convert this problem to calculate maximum subarray sum. If we calculate all the row sum up, then we only need to calculate the maximum subarray sum from all these row sums. Suppose we know row sum from row \(i\) to \(j\) for all columns, and we store it in an array \(rowSum[]\), then we only need to find the maximum subarray for \(rowSum[]\). Now, if we do this for all the row combinations, we get the maximum submatrix sum for the matrix.

    public int largest(int[][] matrix) {

    int m = matrix.length, n = matrix[0].length;
    int[][] rowSum = new int[m+1][n];

    // precalculate the prefix row sum.
    for (int i = 1; i < m+1; i++)
      for (int j = 0; j < n; j++){
      rowSum[i][j] = rowSum[i-1][j] + matrix[i-1][j];
    }

    int maxSum = Integer.MIN_VALUE;
    int [] rangeSum = new int[n];
    for (int i = 0; i < m; i++)
      for (int j = i; j < m ; j++) {
        
        // range row sum from row i to j
        for (int k = 0; k < n; k++)
          rangeSum[k] = rowSum[j+1][k] - rowSum[i][k];

        int sum = 0;

        for (int k = 0; k < n; k++) {
          sum += rangeSum[k];
          if (sum <= rangeSum[k]){
            sum = rangeSum[k];
          }
          maxSum = Math.max(sum, maxSum);
        }
      }

      return maxSum;
    }