Solution

• 贪心算法

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int res = INT_MIN;
        int sum = 0;
        for (int num : array) {
            sum += num;
            res = max(res, sum);
            if (sum < 0) sum = 0;
        }
        return res;
    }
};

• 动态规划

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int n = array.size();
        if (n == 0) return 0;
        int res = 0;
        vector<int> dp(n, 0);  // 以 array[i] 结尾的最大值
        dp[0] = array[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(array[i], array[i]+dp[i-1]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};