某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。

要求实现时间复杂度为 O(n) 的算法。

示例 1：

**输入：**sales = [-2,1,-3,4,-1,2,1,-5,4]
**输出：**6
解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。

示例 2：

**输入：**sales = [5,4,-1,7,8]
**输出：**23
解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。

提示：

1 <= arr.length <= 10^5

-100 <= arr[i] <= 100

动态规划，dp[i]表示以i结尾的最大值，最后返回max(dp[i])即可

dp[i] = max(dp[i-1] + sales[i], sales[i])

dp[i]只与前一个状态和sales[i]有关，所以我们只需要一个变量保存前一状态即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSales(vector<int> &sales) {
        // dp[i] = max(dp[i-1]+sales[i],sales[i])
        int ans = -INT_MAX;
        int pre = 0;
        for (int i : sales) {
            pre = max(pre + i, i);
            ans = max(ans, pre);
        }
        return ans;
    }
};

也可以用滑动窗口加贪心来写

右边界不断右移，每次移动就更新一次最大值，对于左边界当窗口内数为负数时直接缩小左边界至right+1