LC : https://leetcode-cn.com/problems/maximum-subarray/
牛客：https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&&tqId=11183&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路和算法:
**
假设 nums 数组的长度是 n，下标从 0 到 n−1。

我们用 代表 nums[i]，用 代表以第 ii个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

公式 :

因此我们只需要求出每个位置的 ，然后返回 f 数组中的最大值即可。那么我们如何求呢？我们可以考虑
单独成为一段还是加入对应的那一段，这取决于 和+ 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

代码

class Solution {
public:
    int maxSubArray(vector<int> &num) {
        int maxValue = num[0];
        int pre=0;
        for (int i = 0; i < num.size(); ++i) {
            pre = max(pre + num[i], num[i]);
            maxValue = max(maxValue, pre);
        }
        return maxValue;
    }
};