题解 | #子数组的最大累加和问题#

代码

思路：f[i]为从0-n的子数组的最大累加和,同时设一个res，res = 数组中间到数组末尾没有选择的元素的总和
状态计算：f[i]由f[i-1]计算得来
其中：
1.当arr[i] + res < 0 时，f[i]= f[i-1],同时更新res
2.当arr[i] + res >= 0 时：
2.1.res + f[i-1] > 0，即f[i-1]+中间没有选择的元素和大于0，证明res + f[i-1] + arr[i] > arr[i],所以f[i] = f[i-1] + res + arr[i],同时将res=0
2.2.res + f[i-1] <= 0, 即res + f[i-1] + arr[i] <= arr[i], 所以：f[i] = arr[i]，同时将res = 0

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int f[100010];
    int maxsumofSubarray(vector<int>& arr) {
        f[0] = arr[0];
        int res = 0;// res初始为0
        for(int i = 1; i < arr.size(); i++) {
            if(arr[i] + res < 0) {
                f[i] = f[i-1];
                res += arr[i];
            }
            else {
                if ( res + f[i-1] > 0) {
                    f[i] = f[i-1] + res + arr[i];
                    res = 0;
                }   
                else {
                    f[i] = arr[i];
                    res = 0;
                }
            }
        }
//         for(int i = 1; i < arr.size(); i++) cout<<f[i] << endl;
        return f[arr.size()-1];
    } 
};