LeetCode 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.

分析

本题难度为easy难度，但是做起来却是没有那么简单。本题主要是求最大子串的和。如果按照常规遍历的思路，子串的个数为n(n+1)/2个，因此时间复杂度高达O(n2)，而题中要求是O(n)，因此需要使用到divide and conquer，即分治法。

理论基础

问题：对于实数序列array[1...n]，寻找它的一个子串array[i...j]（1<=i<j<=n），s.t. 在array[1...n]的所有子串中，array[i...j]的和最大。

对于该问题的解法，卡耐基梅隆大学的Jay Kadane给出了一个线性时间算法，时间复杂度O(n)。算法的两个结论如下：

1. 对于序列array[1...n]，若array[i...j]为满足要求的和最大子串，那么对于∀k∈[i, j]，有sum(array[i...k]) > 0。

使用反证法对该结论进行证明。
假设∃k∈[i, j]，有sum(array[i...k]) > 0，那么就有
sum(array[k+1...j]) > sum(array[i...k])
这与array[i...j]为和最大子串相矛盾。因此，结论得证。
（此处，对于全是负数的序列，其求和是越来越小，因此只能是最小的一个数和最大，就没有什么意义了。)

2. 对于序列array[1...n]，若array[i...j]为满足要求的和最大子串，那么array[i...j]只能为某个子串的前缀，不可能跨越两个子串。

仍然使用反证法来对该结论进行证明。
假设array[p...q]为满足要求的和最大子串，并且跨越array[i...j]和array[j+1, k]两个子串，根据结论1，有
∃m∈[i, j]，s.t. sum(array[i...m])最大；
∃n∈[j+1, k]，s.t. sum(array[j+1...n])最大。
因此，即比较sum(array[i...m])和sum(array[j+1...n])大小即可。无论大小结果如何，总能找到比array[p...q]更大的和子串，这和array[p, q]是最大子串相矛盾。结论得证。

综上述可知，最大子串为某个子串的前缀，并且大于0。

代码（C语言）

int maxSubArray(int* nums, int numsSize) {
    if (numsSize <= 0)
        return 0;
    
    int maxSum = nums[0];       // 初始设置第一个最大
    int sum = 0;                // 子串的sum
    
    for (int i = 0; i < numsSize; ++i) {
        sum += nums[i];
        maxSum = maxSum > sum ? maxSum : sum;
        
        if (sum < 0)        // 如果子串和小于0，那必有array[k...j]大于0，此处重新计数
            sum = 0;
    }
    
    return maxSum;
}

上述代码中，在循环内部，如果子串和sum小于0，则和结论相违背，置sum=0，重新累加，并且和maxSum进行比较，最终找到最大子串和。