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

//本题用动态规划解决
/*和求最长子序列和一样，可以看一下我上一篇文章，仅仅对子序列的长度做了记录
设置 right ，left ，maxRight ，maxLeft 分别记录实时左右长度和最长的长度
*/

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        //当array长度为1时直接返回
        if(array.length==1){
            return array;
        }
        //记录以array【i】元素结尾的子序列的和的最大值
        int[] dp = new int[array.length];
	  
        int left =0,right = 0;
        int maxLeft  = 0 ,maxRight = 0;
		//初始化dp
        dp[0] = array[0];
	  	//记录最大子和
	  	int max = dp[0];

        for (int i = 1; i < array.length; i++) {
		  //每次运行右边长度默认加一
            right++;
			//因为是连续的子序列，所以当前子序列的和必然和前一个元素的子序列和有关
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]); //状态转移：连续子数组和最大值
		  //当前子序列和更新为array【i】时，前一个子序列结束，重新更新长度
		  //（！注意！）当dp【i-1】== 0时，左右长度不归零更新
            if(dp[i - 1] + array[i] < array[i]) 
                left = right;
		  //题目要的是最长长度，并且是最大的子和
            if (max < dp[i] || max == dp[i] && (maxRight - maxLeft +1) <(right - left + 1) ){
                max = dp[i];
                maxLeft = left;
                maxRight = right;
            }

        }
        int[] ints = new int[maxRight - maxLeft + 1 ];
	  
        for (int j = maxLeft; j <= maxRight ; j++) {
            ints[j - maxLeft] = array[j];
        }
        return ints;
    }
}