动态规划问题
假设数组为
图片说明
图片说明
则整个字符串的最大子串和为:
图片说明
又因为:图片说明
使用自底向上的计算过程,逐次计算Sk的值,取其中的最大值,即为解

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if (array.empty()) {
            return 0;
        }

        int index = array.size() - 1;
        int sum = array[index];
        int maxSum = sum;
        while (--index >= 0) {
            sum = max(sum + array[index], array[index]);
            maxSum = max(sum, maxSum);
        }

        return maxSum;
    }
};