题目

给定一个整数数组 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

解释：
连续子数组 [5, 4, -1, 7, 8] 的和为 23，是最大的。

实现

解法一 - 动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> f(nums.size() , 0);
        f[0] = nums[0];

        int res = f[0];
        for(int i = 1 ; i < nums.size() ; i++)
        {
            // 考虑每个以 i 结尾的串的和 如果f[i-1]大于零 则加上
            // 在这个过程中求最值
            f[i] = max(f[i-1]+nums[i] , nums[i]);
            res = max(res , f[i]);
        }
        return res;
    }
};