53. 最大子序和（动态规划）

绝地灬酷狼 2023-10-05 13:04 8阅读 0赞

#### 53. 最大子序和 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给定一个整数数组 nums ，找到一个具有最大和的**连续子数组**（子数组最少包含一个元素），返回其最大和。  
![在这里插入图片描述][20201102232018982.png_pic_center]

## 解题思路 ##

这是一个子数组问题，首先考虑到用**滑动窗口算法（专门来解决字串/子数组问题）来解决**，但是不可以，因为这题中的数组是负数，当窗口扩大时候可能遇到负数，窗口中的值可能增加也可能减少，这种情况下不知道什么时候去收缩左侧窗口，所以无法求出结果。

故而考虑到这题和**最长递增子序列** 有点类似，于是我们便用动态规划来解决。  
`dp[i]`：以nums\[i\]结尾的“最大子数组和”，可以对照“最长递增子序列”中dp\[i\]的定义

同时呢状态转移方程：`Math.max(nums[i],dp[i-1]+nums[i]);`也是和“300.最长递增子序列”中状态转移方程有点相似。都是考虑 和前面的邻近子数组合并的值比较大，还是自成一派的值比较大

> 举个例子：  
> 比如我现在有数组\[-2,-3,6\]  
> 我现在要求到了dp\[2\]也就是以nums\[2\]结尾的最大子数组和，我之前的子数组和为(－2)+(－3)=－5，而自成一派的和为6。`6>－5`。所以我选择自成一派。

## 代码 ##

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            if(nums.length==0){
        
                return 0;
            }
            int N=nums.length;
            //dp[i]：以nums[i]结尾的“最大子数组和”，可以对照“最长递增子序列”中dp[i]的定义
            int[] dp=new int[N];
    
            //base case
            dp[0]=nums[0];//第一个元素前面没有子数组，所以最大和就是它本身
    
            for(int i=1;i<N;i++){
        
                //要么自成一派，要么和前面的子数组合并
                dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
            }
    
            int res=Integer.MIN_VALUE;
            for(int i=0;i<dp.length;i++){
        
                res=Math.max(res,dp[i]);
            }
    
            return res;
        }
    }

[20201102232018982.png_pic_center]: https://img-blog.csdnimg.cn/20201102232018982.png#pic_center