[数据结构与算法]Java 连续子数组的最大和、动态规划问题

题目： {6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和

解题思路

首先

状态定义：dp[i]?表示以数组下标为i的数做为结尾的连续子数组的最大和注意是以i为结尾

状态解释：比如说现在有一个数组{6,-3,-2,7,-15,1,2,2}，为了方便理解，我们就下标以1开始，dp[3]就是以-2为结尾的，那么显然dp[3]的最大值就是1（6+-3+-2 = 1），dp[4]要以7结尾那么以7结尾的子序列最大和就是8（6+-3+-2+7 = 8。

? 知道dp[i]是什么后，求dp[i]的时候就有两种可能，

????????第一种：就是像上面的dp[4]一样，dp[3]求出来是1了，再加上自己array[4]是最大的。

????????第二种：能就是说如果dp[3]我求出来是负数，那如果我也是dp[3]+array[4]大于d[3]，这时候dp[3]反而是累赘，最大就是array[4]自己。

具体过程：

? ? ? ? （首先我们定义一个max作为每次比较的临时最大值，再用一个maxest?最为历史最大值）

? ? ? ? 第一步：从第一个数array[0]开始，暂且记录一下这个值为最大值。

int max = array[0];
int maxest = array[0];

? ? ? ? 第二步：将目前最大的值（max）+后面一个值（array[i]）和后面这个值（array[i]），进行比较。

for (int i = 1; i < array.length; i++) {
     max = Math.max(max + array[i], array[i]);
     maxest= Math.max(maxest, max);
}

????????如果两者之和（max + array[i]）更大，将两者之和（max + array[i]）进行保留作为临时的最大值。如果这两者之和（max + array[i]）小于后面的值，说明这个max对于array[i]来说是这个“累赘”，所以保留array[i]作为临时的最大值。

? ? ? ? 获得临时最大值max之后，将临时最大值max与历史最大值maxest进行比较，将大的那个作为新的历史最大值maxest。

? ? ? ?最后得到的maxest即为最大连续子数组的和

完整代码：

public class getMax {
    public int getMaxArray(int[] array) {
        //max作为临时最大值
        int max = array[0];
        //maxest作为历史最大值
        int maxest= array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max + array[i], array[i]);
            maxest= Math.max(maxest, max);
        }
        return maxest;
    }
}