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

动态规划的思路，但要注意：每次考虑的元素是包含当前元素的子数组

1. 如果当前子数组和为负数，即便加上当前元素，和也不会变大，因此从当前元素开始开辟新数组；
2. 否则当前子数组加上当前元素合并成新的子数组；
3. 过程中始终维护最大子数组的和及开始与结束的下标

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        vector<int>::iterator p = array.begin(), q = array.begin() + 1;//最大子数组的开始、结束
        vector<int>::iterator a = array.begin(), b = array.begin() + 1;//当前子数组的开始、结束
        int sum = array[0], dp = array[0];//最大子数组总和,当前子数组和
        for(vector<int>::iterator i = array.begin() + 1; i != array.end(); i ++){
            if(dp < 0){
                dp = *i;
                a = i;
                b = i + 1;
            }
            else{
                b = i + 1;
                dp += *i;
            }
            if(dp > sum || (dp ==sum && b - a > q - p)){
                sum = dp;
                p = a;
                q = b;
            }
        }
        vector<int> res(p, q);
        return res;
    }
};