连续最高天数的销售额（动态规划）

某公司每日销售额记于整数数组 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。 

动态规划：

class Solution {
public:
    int maxSales(vector<int>& sales) {
        // 创建dp数组，dp[i]表示以sales[i]为结尾的最大连续子数组和
        vector<int> dp(sales.size());
        
        // 初始化：以第一个元素为结尾的最大子数组和就是它本身
        dp[0] = sales[0];
        
        // 记录全局最大子数组和，初始值为第一个元素的dp值
        int MAX = dp[0];
        
        // 从第二个元素开始遍历数组
        for(int i = 1; i < sales.size(); i++) {
            // 状态转移方程：
            // 要么当前元素单独作为一个子数组（sales[i]），
            // 要么当前元素接在以i-1为结尾的子数组后面（dp[i-1] + sales[i]）
            // 取两种情况中的较大值作为dp[i]
            dp[i] = max(sales[i], dp[i-1] + sales[i]);
            
            // 更新全局最大值，比较当前MAX和新计算的dp[i]
            MAX = max(MAX, dp[i]);
        }
        
        // 返回全局最大子数组和
        return MAX;
    }
};

解析：

一、动态规划核心思路

1. 定义 DP 状态
   定义 dp[i] 表示：以数组第 i 个元素为结尾的最大连续子数组的和。
   这里的「以第 i 个元素为结尾」是关键，它确保了子数组的连续性（必须包含 sales[i]）。

2. 状态转移方程
   对于每个位置 i（i ≥ 1），dp[i] 的值取决于两种情况：

   • 情况 1：从当前元素 sales[i] 重新开始一个子数组（此时子数组仅包含 sales[i]）。
   • 情况 2：将当前元素 sales[i] 加入到「以 i-1 为结尾的子数组」中（此时子数组是 dp[i-1] 对应的子数组加上 sales[i]）。

   因此，状态转移方程为：

   cpp

   运行

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

    

   这意味着：取两种情况中结果更大的一种，作为「以 i 结尾的最优子数组和」。

3. 全局最大值
   用变量 MAX 记录所有 dp[i] 中的最大值，即整个数组的最大子数组和。

二、代码执行步骤（以示例 sales = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例）

1. 初始化

   • dp 数组长度与 sales 相同，dp[0] = sales[0] = -2（第一个元素的最大子数组就是它本身）。
   • MAX 初始化为 dp[0] = -2。

2. 遍历计算（i 从 1 到 8）

   • i=1：
     dp[1] = max(1, dp[0] + 1) = max(1, -2 + 1) = 1（子数组 [1]），MAX 更新为 1。
   • i=2：
     dp[2] = max(-3, dp[1] + (-3)) = max(-3, 1 - 3) = -2（子数组 [1, -3]），MAX 保持 1。
   • i=3：
     dp[3] = max(4, dp[2] + 4) = max(4, -2 + 4) = 4（子数组 [4]），MAX 更新为 4。
   • i=4：
     dp[4] = max(-1, dp[3] + (-1)) = max(-1, 4 - 1) = 3（子数组 [4, -1]），MAX 保持 4。
   • i=5：
     dp[5] = max(2, dp[4] + 2) = max(2, 3 + 2) = 5（子数组 [4, -1, 2]），MAX 更新为 5。
   • i=6：
     dp[6] = max(1, dp[5] + 1) = max(1, 5 + 1) = 6（子数组 [4, -1, 2, 1]），MAX 更新为 6。
   • i=7：
     dp[7] = max(-5, dp[6] + (-5)) = max(-5, 6 - 5) = 1（子数组 [4, -1, 2, 1, -5]），MAX 保持 6。
   • i=8：
     dp[8] = max(4, dp[7] + 4) = max(4, 1 + 4) = 5（子数组 [4, -1, 2, 1, -5, 4]），MAX 保持 6。

3. 返回结果
   最终 MAX = 6，即最大子数组和为 6。

三、复杂度分析

• 时间复杂度：O (n)，其中 n 是数组长度。只需遍历一次数组即可计算所有 dp[i]。
• 空间复杂度：O (n)，用于存储 dp 数组

动态规划（优化）：

class Solution {
public:
    int maxSales(vector<int>& sales) {
        // term 记录以当前元素为结尾的最大连续子数组和（滚动变量，替代dp数组）
        int term = sales[0];
        // MAX 记录全局最大子数组和
        int MAX = term;
        
        // 从第二个元素开始遍历数组
        for(int i = 1; i < sales.size(); i++) {
            // 核心逻辑：
            // 要么从当前元素重新开始一个子数组（取sales[i]），
            // 要么延续之前的子数组（取term + sales[i]），
            // 选择两者中更大的值更新term
            term = max(sales[i], term + sales[i]);
            
            // 每次更新term后，比较并更新全局最大值
            MAX = max(MAX, term);
        }
        
        // 返回全局最大子数组和
        return MAX;
    }
};

1. 滚动变量替代 DP 数组：
   用 term 替代了之前的 dp 数组，它的含义与 dp[i] 完全一致（以当前元素为结尾的最大连续子数组和），但节省了 O (n) 的空间。

2. 初始化逻辑：

   • term 初始化为 sales[0]（第一个元素的最大子数组和就是其本身）。
   • MAX 初始化为 term，记录初始的全局最大值。

3. 核心迭代逻辑：
   对于每个元素 sales[i]：

   • term = max(sales[i], term + sales[i])：决策是否延续之前的子数组，确保 term 始终是 “以 i 结尾的最优解”。
   • MAX = max(MAX, term)：从所有 “以 i 结尾的最优解” 中筛选出全局最大值。

4. 复杂度优化：

   • 时间复杂度仍为 O (n)（遍历一次数组）。
   • 空间复杂度从 O (n) 优化为 O (1)（仅用两个变量），是该问题的最优空间解法。