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

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

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

动态规划求解

思路及代码如下:

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;
}

}

阿勇算法解集 文章被收录于专栏

对一些基础的,经典的题目的算法题解,每道题的题解尽量做到一题多解,举一反三。其中每一个题解中,若是参考了其他牛人的想法,我会备注出来。

全部评论
我觉得 你 很赞,很牛逼!
1 回复 分享
发布于 2022-03-13 11:20

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
07-02 22:46
门头沟学院 Java
码农索隆:hr:“管你投没投,先挂了再说”
点赞 评论 收藏
分享
评论
4
2
分享

创作者周榜

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