题目：

动态规划：

分析：上面的图是老的数组，下面的是新的数组，通过老数组的当前值加上前一个值对应位置的新数组的值，就是新数组对应位置的新值，最后找到新的队列元素中的最大值即可。

代码如下：

#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
	    int length = nums.size();
	    vector<int>resultV(length,0);
	    for(int i = 0; i<length;i++)
	    {
		    if(i == 0)
		    {
			    resultV[i] = nums[i] + 0;
		    }
		    else
		    {
			    resultV[i] = nums[i]+resultV[i-1];
			    if(resultV[i] < nums[i])
			    {
				resultV[i] = nums[i];  // 这部很关键，如果前面的数列之和相加没有原数列对应位置i值大，就需要把原来数列i为hi值，赋给新的数列对应的的i位置上。
			    }
		    }

	    }
	    int max = resultV[0];
       	    for (auto v : resultV)
            {
            	if (max < v)
                max = v;
            }
            return max;
        
    }
};


int main()
{
	Solution way;
	vector<int> nums = {0,-2,5,0,-3,2};
	int result = way.maxSubArray(nums);
	cout <<result<<endl;
	return 0;
}

下面是leetcode解法，原理类似

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;
    }
};