u013096859
「已注销」
2016-04-05 16:31
采纳率: 39.1%
浏览 1.8k
已采纳

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条回答 默认 最新

  • qq_14982047
    在地图上飞行 2016-04-06 02:41
    已采纳

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

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

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

     return maxSubSumRec(array,0,-1);
    

    所以,导致数组越界。

    点赞 评论

相关推荐