题解 | #连续子数组的最大和(二)#

动态规划求解

思路及代码如下：

public class Solution {

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] FindGreatestSumOfSubArray (int[] array) {
    // write code here
    //方法一 动态规划
    int len = array.length;
    int[] dp = new int[len];
    dp[0] = array[0];
    int max = array[0];
    for(int i=1;i<len;++i){
        dp[i] = Math.max(array[i]+dp[i-1],array[i]);
        max = Math.max(dp[i],max);
    }
    int start=-1,end=len-1,j=len-1;
    //从后往前走，找到第一个等于max的下标
    for(;j>=0;--j){
        if(dp[j]==max){
            end = j;
            break;
        }
    }
    //从j-1下标开始继续 从后往前走，找到第一个比0小的数的下标，如果没有就默认是0
    for(j = j-1;j>=0;--j){
        if(dp[j]<0){
            start = j;
            break;
        }
    }
    //最后拼接从[start+1,end]区间内的元素
    int[] path = new int[end-start];
    int index=0;
    for(int i=start+1;i<=end;++i){
        path[index++] = array[i];
    }
    return path;
}

}