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

连续子数组的最大和(二)

https://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21

//本题用动态规划解决
/*和求最长子序列和一样,可以看一下我上一篇文章,仅仅对子序列的长度做了记录
设置 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;
    }
}

动态规划题解 文章被收录于专栏

个人动态规划题解合集

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:23
转人工😡
门口唉提是地铁杀:五次握手了
点赞 评论 收藏
分享
练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务