题
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入: nums = [1] 输出: 1
示例 3:
输入: nums = [5,4,-1,7,8] 输出: 23
- 提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
解法(js):
1、暴力解法遍历
求出所有子序列的和,然后从中挑选出最大的。
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];const maxSub = (arr) => {let maxSum = arr[0];for (let i = 0; i < arr.length; i++) {let sum = 0;for (let j = i; j < arr.length; j++) {sum += arr[j];maxSum = Math.max(maxSum, sum);}}console.log(maxSum);return maxSum;};
2、动态规划
对于最大子序和问题的状态转移方程:
dp[i] = max(nums[i], dp[i-1] + nums[i])
为了理解这个方程是如何确保我们总能获得最大分数的和,我们需要领会动态规划这种算法设计方法的核心思想:最优子结构。
最优子结构是什么意思呢?
在动态规划中,最优子结构意味着一个问题的最优解包含着其子问题的最优解。换句话说,你可以通过组合子问题的最优解来得到整个问题的最优解。
在最大子序和问题中,如果你知道了以nums[i-1]结尾的最大分数和(假设叫它最优子结果),并且现在你面对的新选择是nums[i],那么问题就变成了:
如果这个最优子结果是一个负数,加上nums[i]后总和只会变小,所以我们不如直接从nums[i]开始算起。
如果这个最优子结果是一个正数,那么加上nums[i]后总和会增加,所以我们维持当前子序列,将nums[i]纳入进来。
现在回到状态转移方程。通过持续地更新dp[i],我们总是保持了以nums[i]结尾的最大分数和,对于每一个i:
当你选择nums[i]时,你实际上是重置计数器,从当前这个点开始重新计算子序列(因为你认为之前的序列和对你现在是没帮助的,可能是因为它们是负数)。
当你选择dp[i-1] + nums[i]时,你实际上是选择连续的子序列,并且你相信通过保留之前的序列,新的总和会更大。
该方程确保了你总是取了当前罗列所有可能性中的最大值。通过从左到右遍历数组,你保持了每个子序列的最优解,也因此在每个步骤中,都基于之前的最优解做出了决策。
最终,遍历完成后,数组中包含的dp[i]值中的最大值,就是全局的最大子序和。程序实际上会使用一个变量来记录这个过程中遇到的最大值,因此你不必存储所有的dp[i],只需保持当前的子序列最大和即可。
这样,你可以有信心在完成遍历之后,得到的一定是最大的子序和。这就是动态规划设计方法强大的地方,它确保了你在整个过程中每一步都是基于最优结果做出的选择。
js代码:
const maxSubArrSum = (nums)=>{const maxAns = arr[0];const pre = arr[0]nums.forEach((i) =>{pre = Math.max(pre+i,i); // 如果pre+i < i 说明之前的结果肯定是负数,不如从新的子集开始算maxAns = Math.max(pre,maxAns);} )console.log(maxAns);return maxAns;
}