「已注销」 2016-04-05 16:31 采纳率: 50%
浏览 1824
已采纳

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

 /**
     * 分治递归求解问题: 
     * 分为三种情况:
     *  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);
    }

程序运行结果如下:
图片说明

  • 写回答

1条回答 默认 最新

  • 在地图上飞行 2016-04-06 02:41
    关注

    第二个测试用例中,空数组的长度为0

     return maxSubSumRec(array,0,array.length-1);
    

    这就导致这一步调用传入的实参为

     return maxSubSumRec(array,0,-1);
    

    所以,导致数组越界。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
  • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料