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.

思路

O(n) 即为DP算法，最优子结构为：

cur_sum_max = max(cur_sum_max+num, num)

当前和的最大值 = （前面和的最大值 + 当前值 ）和 当前值之间的较大者。

分治方法的时间复杂度是O(nlgn)

c++11

DP算法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur_sum_max = 0, res_sum_max = INT_MIN;
        for (auto num : nums) {
            cur_sum_max = std::max(cur_sum_max+num, num);
            res_sum_max = std::max(res_sum_max, cur_sum_max);
        }
        return res_sum_max;
    }
};

ac结果：

Runtime: 16 ms, faster than 20.59% of C++ online submissions for Maximum Subarray.
Memory Usage: 10.4 MB, less than 47.92% of C++ online submissions for Maximum Subarray.

分治算法

分治的思想，类似于二分搜索法，我们需要把数组一分为二，分别找出左边和右边的最大子数组之和，然后还要从中间开始向左右分别扫描，求出的最大值分别和左右两边得出的最大值相比较取最大的那一个。

−2,1,−3,4,−1,2,1,−5,4
left       |    right
       crossing

由于子序列连续，它必然属于上述划分中的某一种情况：

• 完全属于 left 部分
• 完全属于 right 部分
• 属于 crossing 部分（即跨越中点）

还没想清楚，具体可参考：https://github.com/pezy/LeetCode/blob/master/052.%20Maximum%20Subarray/divide_conquer.h

http://www.cnblogs.com/grandyang/p/4377150.html