LeetCode | Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

暴力方法：枚举所有子数组，计算子数组和，记下最大的。复杂度是O(n^3)。

思路1：Dynamic Programming

定义f[i]表示以nums[i]结尾的子数组的最大长度。则有

f[i] = f[i-1] + nums[i], when f[i-1] > 0
f[i] = nums[i],          else

由于记忆深度只有1，因此可以将空间复杂度优化到O(1)。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        int f = nums[0];
        int ret = f;
        for (int i = 1; i < n; ++i) {
            f = (f > 0 ? (f + nums[i]) : nums[i]);
            ret = max(ret, f);
        }
        
        return ret;
    }
};

思路2：Prefix Sum

扫描一遍数组的过程中记下当前的前缀和，以及最小的前缀和，两者相减就是当前能够获得的最大子数组和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        int ret = nums[0], sum = 0, min_sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            ret = max(ret, sum - min_sum);
            min_sum = min(min_sum, sum);
        }
        
        return ret;
    }
};

思路3：Divide and Conquer

《编程珠玑》第8章有对该问题详细的探讨。分治法的思想是：将数组划分为左、右两半，于是最大子数组只有3种情形：

1. 完全在左半部分
2. 完全在右半部分
3. 跨越中点

对情形1和2递归求解，比较难计算的是情形3。对于跨越中点的情形，可以发现：最大子数组就是以左半部分的右边界结束的最大子数组，以及以右半部分左边界开始的最大子数组。可以O(n)计算出来。

该方法的递归方程是T(n) = 2T(n/2) + O(n)，其解是T(n) = O(n log n).

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
private:
    int helper(vector<int>& nums, int start, int end) {
        if (start > end) return 0;
        if (start == end) return nums[start];
        
        int mid = start + (end - start) / 2;
        int left = helper(nums, start, mid);
        int right = helper(nums, mid + 1, end);
        
        // find max crossing to left
        int lmax = INT_MIN, sum = 0;
        for (int i = mid; i >= start; --i) {
            sum += nums[i];
            lmax = max(lmax, sum);
        }
        // find max crossing to right
        int rmax = INT_MIN; sum = 0;
        for (int i = mid + 1; i <= end; ++i) {
            sum += nums[i];
            rmax = max(rmax, sum);
        }
        
        return max(max(left, right), lmax + rmax);
    }
};