题目

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

解题思路

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

故而考虑到这题和最长递增子序列 有点类似，于是我们便用动态规划来解决。
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;
    }
}