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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here

        // // 暴力法，时间复杂度失败
        // int val = 0;
        // for(int i = 0; i < array.size(); ++i)
        // {
        //     int sum = 0;
        //     if (i == 0) {
        //         val = array[i]; // 初始化
        //     }
        //     for(int j = i; j < array.size(); ++j)
        //     {
        //         sum += array[j];    // 暴力更新当前节点的子数组
        //         val = max(val, sum);    // 更新最大值
        //     }
        // }
        // return val;

        // 动态规划
        vector<int> dp(array.size(), 0);// 开辟空间，否则dp[0]会非法访问报错
        dp[0] = array[0];
        int sum = 0;
        for(int i = 1; i < array.size(); ++i)
        {
            sum = dp[i-1] + array[i];// 记录当前的子数组的最大值
            // if(sum < 0) sum = 0;
            dp[i] = max(sum, array[i]);// 状态更新并保存当前状态
            // std::cout << i <<" " << dp[i] << std::endl;
        }
        sort(dp.begin(),dp.end());// 递增排序一下，目的把最大值移动到最后面
        return dp[dp.size()-1];//返回最大值
    }
};