Maple's Blog.

Leetcode-53

Leetcode
字数统计: 229阅读时长: 1 min
2019/04/10 Share

maxSubArray-链接

实现的代码如下：

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

这是一道简单的DP，首先从数组的第一个数开始加起，如果是负数的话肯定会越加越小，那么如果sum的值为负数的情况下，就让它重置为0(就相当于舍弃前面的负数了，在此之前如果sum的值有正数的情况，就把它存入到ans中去)，接着sum从0开始继续往后面相加，如果遇到了比前面保存的ans的值更大的话就直接更新ans，最后就直接返回ans的值了。

这里一个很重要的事情就是需要设置一个ans值把上一步的值给保存下来。

原文作者：Maple

原文链接：http://yoursite.com/2019/04/10/leetcode-53/

发表日期：April 10th 2019, 7:05:31 pm

更新日期：April 12th 2019, 9:00:33 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 51
2019
Leetcode 算法与数据结构 C++ 洛谷