题解 | #连续子数组的最大和(二)#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        //1.确定dp数组含义
        //从前往后，遍历到当前位置i最大和是dp[i];
        int dp = 0;

        vector<int> res;//最大连续累加和子数组
        vector<int> tmp;//当前遍历的连续累加和子数组
        int max = -100;//最大连续和 
	  
        //初始化
        dp = array[0];
        //将元素加入当前累加和子数组中
        tmp.push_back(array[0]);

        //递推公式
        for (int i = 1; i < array.size(); i++) {
		  
		  //递推公式
            if (dp >= 0) {
                dp = dp + array[i];
                tmp.push_back(array[i]);
            } else {
                dp = array[i];
                tmp.clear();
                tmp.push_back(array[i]);
            }
		  
		  //维护当前最大连续和子数组
            if (max <= dp) {
                max = dp;
                res = tmp;
            }
        }
	  	//为了防止当数组的长度等于1，导致漏了情况。
        if (dp > max) {
            res = tmp;
        }
        return res;
    }
};