剑指offer42(Java)-连续子数组的最大和（简单）

题目：

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
注意：本题与 力扣 53 题相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

方法一：动态规划

动态规划需要做5步：

①确定dp数组（dp table）以及下标的含义

dp[i]：以nums[i]结尾的最大连续子数组的和

②确定递推公式

dp[i]可以有两个选项：dp[i-1] + nums[i] 或者nums[i]，取两者最大值

• 如果dp[i-1] <= 0，再加上nums[i]的话只会更小，还不如nums[i]，故这时dp[i] = nums[i];
• 如果dp[i-1] > 0，就加上nums[i]，故这时dp[i] = dp[i-1] + nums[i];

③dp数组如何初始化

ddp[i]依赖于dp[i-1]，故将dp[0]作为初始值，且可以假设dp[0] = nums[0]

④确定遍历顺序

从数组的 i = 1开始从后遍历（因为nums[0]已经赋值给dp[0]了）

⑤举例推导dp数组

以  nums = [-2,1,-3,4,-1,2,1,-5,4] 为例：

dp[0] = nums[0] = -2，初始化最大值res = nums[0] = -2 

①dp[1] = max(dp[0] + nums[1], nums[1]) = nums[1] = 1，更新最大值 = 1

②dp[2] = max(dp[1] + nums[2], nums[2]) =dp[1] + nums[2] =  -2，更新最大值 = 不变 = 1

③dp[3] = max(dp[2] + nums[2], nums[2]) = nums[2] = 4，更新最大值 = 4

④dp[4] = max(dp[3] + nums[4], nums[4]) =dp[3] + nums[4] =  3，更新最大值 = 不变 = 4

⑤dp[5] = max(dp[4] + nums[5], nums[5]) = dp[4] + nums[5] = 5，更新最大值 = 5

⑥dp[6] = max(dp[5] + nums[6], nums[6]) = dp[5] + nums[6] = 6，更新最大值 = 6

⑦dp[7] = max(dp[6] + nums[7], nums[7]) = dp[6] + nums[7] = 1，更新最大值 = 不变 = 6

⑧dp[8] = max(dp[7] + nums[8], nums[8]) = dp[7] + nums[8] = 5，更新最大值 = 不变 = 6

最后返回res = 6

代码：

 1 class Solution {
 2     public int maxSubArray(int[] nums) {
 3         //题目明确说过长度大于1，不用判空
 4         int[] dp = new int[nums.length];
 5         //初始化
 6         dp[0] = nums[0];
 7         int res = nums[0];
 8         for (int i = 1; i < nums.length; i++){
 9             //状态转移方程
10             dp[i] += Math.max(dp[i-1]+nums[i], nums[i]);
11             //更新一下最大值
12             res = dp[i] >= res ? dp[i] : res;
13         }
14         return res;
15     }
16 }

转移状态的重点在于：若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。

可以看看：k神老师的题解

方法二：贪心法

贪心算法的本质：只考虑局部最优

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”，局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

 思路：遍历数组nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。

代码：

 1 class Solution {
 2     public int maxSubArray(int[] nums) {
 3         if (nums.length == 1) return nums[0];
 4         int count = 0,res = Integer.MIN_VALUE;
 5         for (int i = 0; i < nums.length; i++){
 6             count += nums[i];
 7             //更新一下最大值
 8             res = Math.max(res,count);
 9             if(count < 0){
10                 count = 0;
11             }
12         }
13         return res;
14     }
15 }

小知识：

①动态规划：

知识详情解释可以看看：代码随想录

动态规划需要做5步：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

②贪心法：详情解释：代码随想录贪心算法