53 Maximum Subarray

title: Maximum Subarray
tags:
- maximum-subarray
- No.53
- simple
- divide-conquer
- mathematical-analysis

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Corner Cases

empty array
all negative
all positive

Solutions

Divide and Conquer

For input array nums[], we can compute the sum array sums[] s.t.

sums[0] = 0;
sums[1] = 0 + nums[0];
sums[2] = 0 + nums[0] + nums[1];
sums[3] = 0 + nums[0] + nums[1] + nums[2];

and

nums[0] = sums[1] - sums[0];
nums[1] = sums[2] - sums[1];
nums[2] = sums[3] - sums[2];

Then any sum of continuous elements nums[i] + ... + nums[j] can be represented by sums[j+1] - sums[i]. Then, we can do divide and conquer more quickly.

Note that we must make sure that i <= j.

For any range [i : j] for sums, we divide it into two halves: [i : k] and [k+1 : j]. Then we have:

divideConquer(i, j) = max{ 
    divideConquer(i, k),
    divideConquer(k+1, j),
    max{sums[jj] - sums[ii]} // ii \in [i : j] && jj \in [k+1 : j]
}

It's obvious that:

max{sums[jj] - sums[ii]} = max{sums[k+1 : j]} - min{sums[i : j]}

This conclusion can be computed within $O(n)$ time. Thus we have $T(n) = 2 \times T(\frac{n}{2}) + O(n)$ . The running is $T(n) = O(n \lg(n))$ :

class Solution {
    private int[] sums;

    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {return -2147483648;}

        sums = new int[1 + nums.length];
        for (int i=0, s=0; i<nums.length; i++) {
            s         = s + nums[i];
            sums[1+i] = s;
        }

        return divideConquer(0, sums.length-1);
    }

    public int divideConquer(int i, int j) {
        if ((i==j) || (i==0 && j==1)) {
            return sums[j]-sums[j-1];
        }

        int k = (i + j)/2;
        int a = divideConquer(i, k);
        int b = divideConquer(k+1, j);

        int cmax = -2147483648;
        int cmin = 2147483647;
        for (int jj=k+1; jj<=j; jj++) {
            cmax = (sums[jj] < cmax) ? cmax : sums[jj];
        }
        for (int ii=i; ii<=k; ii++) {
            cmin = (cmin < sums[ii]) ? cmin : sums[ii];
        }
        int c = cmax - cmin;

        return (((a > b) ? a : b) > c) ? ((a > b) ? a : b) : c;
    }
}

Zero Points

For continuous variable $t$ and continous integralable function $f(t)$ and the definite integral $\int_{y}^{x} f(t)dt = F(x) - F(y)$ , we have:

$\frac{\partial F(x) - F(y)}{\partial x} = \frac{dF}{dx}(x) = f(x) = 0$

$\frac{\partial F(x) - F(y)}{\partial y} = \frac{dF}{dy}(y) = f(y) = 0$

This is the relationship of the Force and Work. That is to say: we sometimes do positive work, sometimes do negative work, and want to figure out the largest Potential difference. Since the extremums occur at zeros of derivative function, we check nums for changing signs.

[-2, 1,-3, 4,-1, 2, 1,-5, 4]
 **0** **2** **4** **6**
    **1** **3** **5** **7**

We have 8 pairs of zeros to check here above. This method is bad when zeros are close to each other, but relative good when they are sparse.