动态规划.4

题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

• 进阶:
• 
  

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

分析

指定输入数组为array，结果数组是result
从前往后分析：

1. 如果只有第一个元素，那么最大的子串值为-2
2. 如果有2个元素，那么最大的字串值为max{1,-2,1-2}，最大值为1；
3. 如果有3个元素，那么最大的值，等于有2个元素的时候，加上第三个元素的值（第三个元素的值>0），如果第三个元素的值小于0，那么最大的值还是前两个元素子串的最大值

递归分析：
如果想要得知包含n个内容的数组最大子串和，就需要得知n-1个元素的最大子串和，如果第n个元素>0，最终结果加上n的值即可，n的值<0的话，那无需处理；
上述这种想法是错误的….按照这种想法，前四个元素的最大值应当是5，但是实际上并不是…因为-2，1，-3，4，中，1和4并不相邻…他们中间隔着一个-3，如果要算子串，那么应当是1，-3，4，和是2….这很明显不是那么合理，子串的一个重要特征是，元素在原本的数组中就是相邻的
换一种思路：出现最大的情况是什么时候？

1. 我们分析前四个元素，-2，1，-3，4；最大的子串是4，就单单是第四个元素，不算第123个元素…这种情况最大；
2. 逐个分析：
3. 数组长度=1，max=-2；result[0]=-2;result={-2}
4. 数组长度=2，max=1；result[1]=1;result={-2,1}
5. 数组长度=3，max就有的分析了…
6. 如果把元素3并入最大值，那么此时result[2]=result[1]+array[2]，如果不并入元素3，那么最大值就是元素3本身的值….因为和之前的元素联系断了,result[2]=array[2]；
7. 我们要做的，就是比较result[1]+array[2]和array[2]的大小
8. 换句话说，我们做的是，确定是否将第n个元素和第n-1个元素连起来

按照这个逻辑，当array={1，2，3，-1，2}的时候，result的取值

1. {1}
2. {1，3}//连起来了，累加
3. {1，3，6}//连起来，累加
4. {1，3，6，5}//取本身（-1）和连起来的值（-1+6）中较大的值（5）
5. {1，3，6，5，7}//取本身(2)和连起来的值（5+2）中较大的值（7）

动态规划，并不一定要使用递归

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        //定义dp数组，dp数组中的每个值dp[i]代表着以nums[i]为结尾的最大子序和
        int[] dp = new int[n];
        //以nums[0]结尾的最大子序和就是nums[0]
        dp[0] = nums[0];
        //遍历，通过状态转移方程求得dp[i]的最大子序和
        for(int i = 1; i < n; ++i){
            //dp[i]的最大子序和要么是自成一派最大，要么就是当前值加上前面i - 1个数的最大子序和
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        //遍历dp数组，求得dp数组中的最大值，就是该题的答案
        int res = Integer.MIN_VALUE;
        for(int j = 0; j < dp.length; ++j){
            res = Math.max(res, dp[j]);
        }
        return res;
    }
}