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.

用一個dp array去紀錄，dp[i]代表以nums[i]結尾的subarray裡最大的和。如果dp[i - 1]是負數，代表到nums[i - 1]結尾的subarray裡，最大的和都是負的，那這樣下一個nums[i]就可以不要取前面的subarray，直接重新開始一個新的subarray。

int maxSubArray(vector<int>& nums) { // time: O(n); space: O(n)
    int n = nums.size();
    vector<int> dp(n, 0); // dp[i]: max sum of subarray ending with nums[i]
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = (dp[i - 1] > 0 ? dp[i - 1] : 0) + nums[i];
        res = max(res, dp[i]);
    }
    return res;
}

DP的想法，不過優化空間的使用，注意一開始res不能初始化成0，因為有可能整個array裡的數都是負數，這樣會取不到裡面最大的負和，所以要初始化成array裡第一個數是最安全的。

int maxSubArray(vector<int>& nums) { // time: O(n); space: O(1)
    int sum = 0, res = nums[0];
    for (int num : nums) {
        sum += num;
        res = max(res, sum);
        if (sum < 0) sum = 0;
    }
    return res;
}

Divide and Conquer的方法。

int maxSubArray(vector<int>& nums) { // time: O(nlogn); space: O(logn)
    if (nums.empty()) return 0;
    return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector<int>& nums, int l, int r) {
    if (l >= r) return nums[l];
    int mid = l + (r - l) / 2;
    int lmax = helper(nums, l, mid - 1);
    int rmax = helper(nums, mid + 1, r);
    int mx = nums[mid], sum = nums[mid];
    for (int i = mid - 1; i >= l; --i) {
        sum += nums[i];
        mx = max(mx, sum);
    }
    sum = mx;
    for (int i = mid + 1; i <= r; ++i) {
        sum += nums[i];
        mx = max(mx, sum);
    }
    return max({mx, lmax, rmax});
}