53. Maximum Subarray

发表于 | 分类于 | |

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

题意：找出和最大的连续子序列。

​ 这道题其实一个月前开始就开始写了 ，但是错了好多次。之前想的是，不就是求Sum[i…j]最大嘛，那直接遍历所有i和j的所有可能取值就行了。复杂度为O（n^2），理所当然的超时了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum;
        int n = nums.size();
        int ans = -2147483647;
        for (int i = 0; i < n ; ++i)
        {
            sum = 0;
            for (int j = i ; j < n; ++j)
            {
                sum +=  nums[j];
                ans = max(sum, ans);
            }
        }
        return ans;
    }
};

​ 刚好这两天做了一道十分相似的题目：560. Subarray Sum Equals K ，了解到了前缀和这种神奇的东西。所以一个月后再来看这道之前一直没解决的问题，还是觉得当时实在是太naive了。这不也就利用前缀和就可以在O（N）的复杂度内解决的么？

​ 假设sum以是j为结尾的前缀和，那么只需要减去j以前的最小的前缀和，那么就可以得到以j为结尾的和最大连续子序列。遍历每个j，然后维护最大值就ok啦~~注意：preSum[-1] = 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxSubArray(vector<int> &nums)
    {
        int len = nums.size();
        if (!len)
            return 0;
        if (len == 1)
            return nums[0];
        else
        {
            int sum = nums[0];
            int minPreSum = min(0, nums[0]);
            int ans = nums[0];

            for (int i = 1; i < nums.size(); i++)
            {
                sum += nums[i];
                ans = max(ans, sum - minPreSum);//维护子序列和最大值
                minPreSum = min(sum, minPreSum);//维护j之前的最小子序列和
            }
            return ans;
        }

    }
};