2 u013096859 u013096859 于 2016.04.06 00:31 提问

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

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

2个回答

qq_14982047
qq_14982047   2016.04.06 10:41
已采纳

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

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

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

 return maxSubSumRec(array,0,-1);

所以,导致数组越界。

u013096859
u013096859 666,思维一直局限在递归逻辑的检查了,非常感谢
一年多之前 回复
CSDNXIAOD
CSDNXIAOD   2016.04.06 00:41

最大子序列问题及其求解
最大子序列和问题的求解
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!