题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray

题解

       我的理解 ： 动态规划，f(i)=f(i-1)+nums[i] 与 nums[i] 的最大值，这可以保证f(i)永远是最大的，这样从数组的第一个数开始，保证每个f(i)都是最大的，那么结果也就能出现的。<br />        ｛ 例如1：f(1) = 3 , nums[2] = -1 ，这时f(2) = 2 ｝<br />   它的意思是，从nums[1]开始参与运算得到的结果要比从nums[2]开始参与运算得到的结果要好，如例1，从1开始，到nums[3]，参与运算的就是2 ，但是从nums[2]开始的话，参与运算的就是-1，显然不划算。。<br />｛例如2：f(1) = -1 , nums[2] = 1 ，这时f(2) = 1 ｝<br />   因为从1开始，到nums[3]，参与运算的就是-1+1=0了 ， 但是nums[2]是大于0的，所以，从2开始划算。。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
            for (const auto &x : nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};