53. Maximum Subarray

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.

中文

给定数组a[1...n]，求最大子数组和，即找出 1<= i <= j <= n，使a[i]+a[i+1]+...a[j]最大

介绍三种算法

暴力枚举O(n³)

优化枚举O(n²)

贪心法O(n)

暴力枚举（三重循环）

时间复杂度为(n³)， 空间复杂度O(1)

伪代码  
for i <- 1 to n
    for j <- 1 to n
        sum <- a[i]+...a[j]
        ans <- max(ans,sum)

public int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0)
            return -1;
        int ans = -2147483647;
        int n = nums.length;
        for(int st=0; st<n;++st){
            for(int ed=st+1; ed<=n; ++ed){
                int sum = 0;
                for(int i = st; i<ed; ++i){
                    sum+=nums[i];
                }
                if(sum>ans)
                    ans=sum;
            }
        }
        return ans;
}

submission detail

当数据太大时，运行会超时。

枚举优化（二重循环）

三重循环的时间复杂度太高，而每一次计算子数组和都需要重新计算一遍之前的 sum。

[-2,1,-3,4,-1,2,1,-5,4]
st=2,ed=3  sum = a[2]+a[3]
st=2,ed=4  sum = a[2]+a[3]+a[4]

显然 a[2]+a[3进行了重复计算，ed每次增加，都需要反复增加。

优化 将前一次计算的和存储在 ans 中

时间复杂度为(n²)， 空间复杂度O(1)

伪代码  
for i <- 1 to n
    sum <- 0
    for j <- 1 to n
        sum <- sum + a[j]
        ans <- max(ans,sum)

public int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0)
            return -1;
        int ans = -2147483647;
        int n = nums.length;
        for(int st=0; st<n; ++st){
            int sum = 0;
            for(int ed=st+1; ed<=n; ++ed){
                // int sum = 0;
                // for(int i = st;i<ed;++i){
                //     sum+=nums[i];
                // }
                sum += nums[ed-1];//将上一次结果存储在 sum 中
                if(sum>ans)
                    ans=sum;
            }
        }
        return ans;
}

submission detail

贪心法（一重循环）

时间复杂度为(n)， 空间复杂度O(1)

伪代码  
sum <- 0, ans <- 0
for i <- 1 to n
    sum <- sum + a[i]
    ans <- max(ans,sum)
    if(sum < 0) sum <- 0
    
要实现最大的子数组和[i，j]，转换成求 [i,j] - min[0,i-1]，在 [0，i-1] 区间找到一个最小的值，最终得到一个最大的值。

public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return -1;
        int ans = -2147483647;
        int sj = 0;
        int minSi = 0;
        int si=0;
        int n = nums.length;
        //要求 max[i,j] = a[i] + ... a[j]，
        //转换成 max[sj - min(si)] , sj[i,j] = a[i] +...+ a[j], si[0,i-1] = a[0] +...+ a[i-1] 
        // max = sj[i,j] - min(si[0,i-1])
        //将求最大转换成减去一个最小值
        for(int j = 0; j < n; ++j){ //min[0,6] = min(min[0,5] , min[6,6])
            sj += nums[j];  //计算sj
            if(si < minSi)  //取最小的 si
                minSi = si;
            if(sj - minSi > ans) //ans = sj - minSi， 此时，存储的 ans 最大
                ans = sj - minSi;
            si += nums[j];  //计算 si
        }
        return ans;
}

public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return -1;
        int ans = -2147483647;
        int sj = 0;
        int minSi = 0;
        int si=0;
        int n = nums.length;
        int sum = 0          // si - minSi;
        for(int j = 0; j < n; ++j){ 
            if(sum < 0)    // if(si - minSi < 0)
                sum = 0;
            if(sum + nums[j] > ans)  // s[j] = si + nums[j]
                ans = sum + nums[j];  //maxSum = sum + nums[j]
            sum += nums[j];
        }
        return ans;
}

//上面那个算法和下面这个贪心算法类似，做一些等量替换
public int maxSubArray4(int[] nums) {
        if(nums == null || nums.length == 0)
            return -1;
        int sum = 0;
        int maxSum = -2147483647;
        int n = nums.length;
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            if(sum > maxSum) {
                maxSum = sum;
            }
            if(sum < 0){
                sum = 0;
            }
        }
        return maxSum;
    }