LeetCode 53 最大子序和

题面描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

题解

如果已知以位置$结尾的子数组的最大和，怎么求以位置i结尾的子数组的最大和呢？

• 一种情况是把这个位置的数和前面的子数组加起来
• 另一种情况是不要之前的子数组。只要位置上的这个数

这样遍历一遍之后就可以得到以每个位置结尾的子数组的最大值了，然后这里面最大的那一个就是题目所找的具有最大和的连续子数组。

#include<iostream>
#include<vector>
using namespace std;

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

int main()
{
    Solution s;
    vector<int> num={-2,1,-3,4,-1,2,1,-5,4};
    cout<<s.maxSubArray(num);
    return 0;
}