题目：
{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和解题思路
万物皆可使用暴力法，暴力法还是比较容易的，O（n^2）的时间复杂度，我是满足的，但是面试官显然不满足，使用动态规划可以是复杂度到O（n）。
博主看了几篇关于最大连续子序列的和的博客，发现都是上来给出状态方程：
max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] ) 这谁顶的住啊，尤其是像博主这种算法能力很差的同学。
首先我们需要了解dp[i]到底是个啥，经过博主的不懈努力，终于发现dp[i]就是以数组下标为i的数做为结尾的最大子序列和，注意是以i为结尾，比如说现在有一个数组{6,-3,-2,7,-15,1,2,2}，为了不搞，我们就下标以1开始，dp[3]就是以-2为结尾的，那么显然dp[3]的最大值就是1咯（6，-3，-2），dp[4]要以7结尾那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
知道dp[i]是啥后，现在我们开始细细品一下上面这个递推式，求dp[i]的时候是不是有两种可能，要么就是像上面的dp[4]一样，dp[3]求出来是1了，再加上自己array[4]是最大的，那么还有一种可能就是说如果dp[3]我求出来是-100，那如果我也是dp[3]+array[4]的话是-93，这时候dp[3]反而是累赘，最大就是自己（因为前面定义了必须以i为结尾，也就说必须以7结尾）。
代码实现
/**
* dp dp(i)=max(dp(i-1)+array[i],array[i])
* {6,-3,-2,7,-15,1,2,2},
* @author dingyu
*/
public class T29 {
public int FindGreatestSumOfSubArray(int[] array) {
//max就是上面的dp[i]
int max = array[0];
//因为这个dp[i]老是变，所以比如你dp[4]是8 dp[5]就变成-7了，所以需要res保存一下
int res = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max + array[i], array[i]);
res = Math.max(res, max);
}
return res;
}
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
