LCR 161.销售区域最大销售额
难度：🟡 中等
标签：数组、分治、动态规划
链接：LCR 161. 销售区域最大销售额 (剑指 Offer 42. 连续子数组的最大和)
题目描述
给定一个整数数组 sales，代表每个销售区域的销售额。请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），并返回其最大和。
示例 1：
输入：sales = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2：
输入：sales = [1]
输出：1
示例 3：
输入：sales = [5,4,-1,7,8]
输出：23
解题思路
核心思想
本题的目标是找到一个数组中和最大的连续子数组。这个问题的核心是动态规划，具体来说是经典的 Kadane's 算法。其思想是，当我们遍历数组时，对于每个元素，我们都做出一个决定：是将当前元素加入到之前的子数组中，还是从当前元素开始一个新的子数组。
思路选择
动态规划 是解决此问题的最优思路。
我们定义
dp[i]为以sales[i]结尾 的连续子数组的最大和。状态转移方程为：
dp[i] = max(sales[i], dp[i-1] + sales[i])。sales[i]：表示从当前元素开始一个新的子数组。dp[i-1] + sales[i]：表示将当前元素加入到上一个以sales[i-1]结尾的子数组中。
我们选择这两者中的较大值。如果
dp[i-1]是负数，那么dp[i-1] + sales[i]肯定比sales[i]小，此时就应该舍弃前面的子数组，从sales[i]开始新的征程。由于
dp[i]只与dp[i-1]有关，我们可以用一个变量curValue来代替整个dp数组，进行空间优化。
关键步骤
初始化：初始化全局最大和
maxValue和当前连续子数组和curValue都为第一个元素sales[0]。循环遍历：从第二个元素（索引
i = 1）开始遍历数组。 a. 更新当前和：计算sales[i]和curValue + sales[i]的较大值，并更新curValue。这相当于决定是“自立门户”还是“加入团伙”。 b. 更新全局最大和：用更新后的curValue来挑战并更新全局的maxValue。返回结果：遍历结束后，
maxValue中存储的就是整个数组中连续子数组的最大和。
代码实现
/**
* @param {number[]} sales
* @return {number}
*/
var maxSales = function (sales) {
// 初始化最大值和当前值为第一个元素
let maxValue = sales[0];
let curValue = sales[0];
for (let i = 1; i < sales.length; i++) {
// 更新当前连续子数组的最大和
curValue = Math.max(sales[i], curValue + sales[i]);
// 更新全局最大和
maxValue = Math.max(curValue, maxValue);
}
return maxValue;
};
复杂度分析
时间复杂度：O(n) 其中 n 是数组
sales的长度。我们只需要对数组进行一次完整的遍历。空间复杂度：O(1) 我们只使用了
maxValue和curValue两个额外变量，空间消耗是恒定的。
相关题目
总结
本题是动态规划的经典入门题，Kadane's 算法是其标准解法。通过维护一个“以当前元素结尾的子数组的最大和”，并在此基础上不断更新全局最大和，算法以线性的时间和常数的空间解决了问题，非常高效。