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

要求空间复杂度为 O（1），反而是个提示，因为这意味着只能用几个变量记录值。很明显一个记录是不可能的，所以先定义两个

// 使用两个临时变量记录
int maxSum = arr[0];
int tmpSum = arr[0];

然后，时间复杂度是 O（n），以为着用的 只能是一重循环
关键：

当前面的子数组和为负数时，中断重新开始求和。

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        // 使用两个临时变量记录
        int maxSum = arr[0];
        int tmpSum = arr[0];

        for (int i = 1; i < arr.size(); i++) {
            // 如果子数组小于 0，重置数组
            if (tmpSum < 0)
                tmpSum = arr[i];
            // 否则，加上数组元素的值
            else
                tmpSum += arr[i];


            // 
            if (tmpSum > maxSum)
                maxSum = tmpSum;
        }

        return maxSum;
    }
};