53. 最大子数组和

难度中等5619

给你一个整数数组 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

动态规划

• dp数组的定义 : 以nums[i]为结尾的最大连续子数组之和为dp[i]
• dp数组的状态转移方程 : 对于一个元素最大连续子数组要么是本身,要么是以nums[i-1]为结尾最大的子数组之和加上本身 dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
• dp数组初始化 : 由于状态转移方程要知道dp[i-1]得状态,所以要初始化dp[0],当数组长度为1的时候最大子数组之和为nums[0] 即 dp[0] = nums[0]
• dp数组遍历顺序 : 根据动态转移方程 想要推出dp[i],既要知道dp[i-1]也就是前一个的状态,所以从左往右遍历即可
• 因为dp[i]只计算出以nums[i]为结尾的最大子数组之和,所以我们要想求出整个数组的最大子数组这和,需要一个max变量更新最大子数组之和

class Solution {public int maxSubArray(int[] nums) {if(nums.length<=1){return nums[0];}//dp:以nums[i]为结尾的最大子数组之和为dp[i]int[] dp = new int[nums.length];dp[0] = nums[0];//dp初始化,一个元素的时候最大子数组之后就是自己(nums[0])int max = nums[0];//初始化最大子数组之和for(int i =1;i