java 求最大子序列和问题递归求解报越界异常-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

java 求最大子序列和问题递归求解报越界异常

2016-06-08 14:31:24 1707 1
 /**
     * 分治递归求解问题: 
     * 分为三种情况:
     *  1.最大子序列出现在左半边部分 
     *  2.最大子序列出现在右半边部分
     *  3.最大子序列出现在中间部分,此时取两边的最大子序列的和之和(左边子序列包含最后一个元素,右边子序列包含第一个元素)
     * 
     * @param array
     * @return
     */
    public static int maxSubSum1(int[] array) {
        return maxSubSumRec(array,0,array.length-1);
    }

    /**
     * 闭区间
     */
    private static int maxSubSumRec(int[] array, int left, int right) {
        if(left==right)
            return array[left]>0?array[left]:0;

        int center = (left+right)/2;
        System.out.println(left+" "+center+" "+right);
        int maxLeft = maxSubSumRec(array,left,center);      //左侧子串和最大值

        int maxRight = maxSubSumRec(array,center+1,right);      //右侧子串和最大值

        //中间部分最大值
        int maxLeftFromCenter = 0,maxRightFromCenter = 0;
        for(int i=center,currentSum = 0;i>=left;i--)
        {
            currentSum+=array[i];
            if(currentSum > maxLeftFromCenter)
                maxLeftFromCenter = currentSum;
        }
        for(int i=center+1,currentSum = 0;i<=right;i++)
        {
            currentSum+=array[i];
            if(currentSum > maxLeftFromCenter)
                maxRightFromCenter = currentSum;
        }
        int maxCenter = maxLeftFromCenter+maxRightFromCenter;

        return Math.max(Math.max(maxLeft, maxCenter),maxRight);
    }

程序运行结果如下:
screenshot

取消 提交回答
全部回答(1)
  • 蛮大人123
    2019-07-17 19:31:56

    第二个测试用例中,空数组的长度为0
    return maxSubSumRec(array,0,array.length-1);
    这就导致这一步调用传入的实参为
    return maxSubSumRec(array,0,-1);
    所以,导致数组越界。

    0 0
相关问答

40

回答

[@徐雷frank][¥20]什么是JAVA的平台无关性

大河人家 2018-10-29 23:55:20 144790浏览量 回答数 40

162

回答

惊喜翻倍:免费ECS+免费环境配置~!(ECS免费体验6个月活动3月31日结束)

豆妹 2014-10-29 17:52:21 226286浏览量 回答数 162

8

回答

OceanBase 使用动画(持续更新)

mq4096 2019-02-20 17:16:36 337139浏览量 回答数 8

13

回答

[@饭娱咖啡][¥20]我想知道 Java 关于引用那一块的知识

心意乱 2018-10-31 18:44:12 142497浏览量 回答数 13

111

回答

OSS存储服务-客户端工具

newegg11 2012-05-17 15:37:18 295724浏览量 回答数 111

22

回答

爬虫数据管理【问答合集】

我是管理员 2018-08-10 16:37:41 147296浏览量 回答数 22

18

回答

阿里云开放端口权限

xcxx 2016-07-20 15:03:33 646922浏览量 回答数 18

31

回答

[@倚贤][¥20]刚学完html/css/js的新手学习servlet、jsp需要注意哪些问题?

弗洛伊德6 2018-10-27 21:52:43 146096浏览量 回答数 31

42

回答

【精品问答集锦】Python热门问题

小六码奴 2019-05-30 15:27:34 137228浏览量 回答数 42

10

回答

[@墨玖tao][¥20]为什么流式处理框架都是 java 写成的,JVM 是不是在流和批存在着特殊优势。还有分布式资源调度,感觉Mesos 的成长速度跟不上 Yarn。这是为什么?

管理贝贝 2018-10-23 13:18:03 136503浏览量 回答数 10
+关注
蛮大人123
我说我不帅他们就打我,还说我虚伪
0
文章
7733
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载