剑指 Offer 42. 连续子数组的最大和（动态规划）
2021-04-13 15:29
标签：turn 连续 一个 style 时间复杂度 描述 输入 ret 负数 https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/ 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 （1）定义状态： 假设 dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列） ?以 nums[0] –2 结尾的最大连续子序列是 –2，所以 dp(0) = –2 （2）状态转移方程： 如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i] （3）初始状态： dp(0) 的值是 nums[0] （4）最终的解： 最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length) 剑指 Offer 42. 连续子数组的最大和（动态规划） 标签：turn 连续 一个 style 时间复杂度 描述 输入 ret 负数 原文地址：https://www.cnblogs.com/guoyu1/p/13340521.html1、题目描述：
2、示例1:
3、思路：
? 以 nums[1] 1 结尾的最大连续子序列是 1，所以 dp(1) = 1
? 以 nums[2] –3 结尾的最大连续子序列是 1、–3，所以 dp(2) = dp(1) + (–3) = –2
? 以 nums[3] 4 结尾的最大连续子序列是 4，所以 dp(3) = 4
? 以 nums[4] –1 结尾的最大连续子序列是 4、–1，所以 dp(4) = dp(3) + (–1) = 3
? 以 nums[5] 2 结尾的最大连续子序列是 4、–1、2，所以 dp(5) = dp(4) + 2 = 5
? 以 nums[6] 1 结尾的最大连续子序列是 4、–1、2、1，所以 dp(6) = dp(5) + 1 = 6
? 以 nums[7] –5 结尾的最大连续子序列是 4、–1、2、1、–5，所以 dp(7) = dp(6) + (–5) = 1
? 以 nums[8] 4 结尾的最大连续子序列是 4、–1、2、1、–5、4，所以 dp(8) = dp(7) + 4 = 5
如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]4、代码：
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i ) {
if (dp[i - 1] ) {
dp[i] = nums[i];
} else {
dp[i] = dp[i - 1] + nums[i];
}
max = Math.max(dp[i], max);
}
return max;
}
}
文章标题：剑指 Offer 42. 连续子数组的最大和（动态规划）
文章链接：http://soscw.com/index.php/essay/75259.html