输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

算法1

DP

分为3个状态即可DP

ans[j]为以位置j结束的连续子数组的最大和

由上图分析出在位置j的连续子数组的最大和可能有3种状态得出

1：由j-1位置的数加上j位置的数。
2：由以j-1位置结尾的连续子数组的和加上j位置的数。
3：j位置数本身最大。因此可得

ans[ j ]=max(nums[ j ],nums[ j-1 ]+nums[ j ],ans[ j-1 ]+nums[ j ]);

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

    }
};