！！！题解 | 连续子数组的最大和 妙 一开始没啥思路 可以多看看这道

#include <climits>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        //不能排序 会破坏数组之间的邻居关系
        //没啥思路
        /*能够想到的是，可以以当前元素作为这个目标序列的结尾。
        但是这样DP数组应该定义为什么呢，他肯定要继承前面的那个数字，
        但是这样的话是不是就觉得，只能是从开头起到这个元素的和，不知道从哪里断掉，没有办法对这个数列从哪里开头进行操作？
        先看一个例子，就是这个数组是从左往右遍历的，我们不知道右边的序列是怎么样的，只知道最左边的是一个正数还是负数，那么我们还要不要以左边这个负数为这个序列的开头？
        不可以，因为加入它就会让这个最大和变小，所以不应该以左边那个负数开头，
        而应该以当前元素开头。所以这样就对这个子数组从哪里开头做了正确的处理。
        */
        int size=array.size();
        if(size==1)return array[0];
        int res=INT_MIN;//这里其实可以让它等于dp0；就不用做上面那个判断了
       
        //长度最小=1.
        vector<int> dp(size);
        dp[0]=array[0];
        for(int i=1;i<size;i++){//从1开始是正确的
            if(dp[i-1]>0)dp[i]=dp[i-1]+array[i];
            else{
                dp[i]=array[i];
            }
            if(dp[i]>res)res=dp[i];
        }
        return res;
    }
};