package maxSub;public class Max3 {
private static int maxSumRec(int[] a, int left, int right)
{
if(left == right)
if(a[left]>0)
return a[left];
else
return 0;

int center = (left+right)/2;
int maxLeftSum = maxSumRec(a,left,center);
int maxRightSum = maxSumRec(a,center+1,right);

int maxLeftBorderSum= 0, leftBorderSum = 0;
for(int i =center;i>=left;i--)
{
leftBorderSum += a[i];
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}

int maxRightBorderSum =0, rightBorderSum = 0;
for(int i = center+1;i<=right;i++)
{
rightBorderSum +=a[i];
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}

return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightSum);
}

public static int max3(int a,int b,int c)
{
int temp = 0;
temp= a>b ? a:b;
temp= temp>c ? temp :c;
return temp;
}

public static void main(String[] args)
{
int [] a={4,-3,5,-2,-1,2,6,-2};
System.out.println(maxSumRec(a,0,a.length-1));
}}
还有这个我为什么最后得到的结果是12?应该是11的啊。。
谢谢朋友了!

解决方案 »

  1.   

      --return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightSum);
    第三个参数??
        return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
      

  2.   

    是啊,应该是return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
    maxRightSum是8,所以你得到12了,maxRightBorderSum才是7。
      

  3.   

    楼主的算法太麻烦,给你写个简单的,循环一遍下来就OK.public static void main(String[] args){
            int[] A ={4,-3,5,-2,-1,2,6,-2};
            int begin_index = 0;
            int end_index = 0;
            int temp_sum = A[0];
            int temp_max = A[0];
            
            for(int i = 1; i < A.length; i++){
                int a = temp_max;
                int b = temp_sum + A[i];
                int c = A[i];
                if(a >= b && a >= c){//a最大
                    temp_sum += A[i];
                }
                else if(b >= a && b >= c){//b最大
                    end_index = i;
                    temp_sum = temp_max = b;
                }
                else{//c最大
                    begin_index = end_index = i;
                    temp_sum = temp_max = A[i];
                }
            }
            System.out.print("最长子序列: ");
            for(int i = begin_index; i <= end_index; i++){
                System.out.print(A[i] + " ");
            }
            System.out.println();
            System.out.println("最长子序列的和 = " + temp_max);
        }输出:
    最长子序列: 4 -3 5 -2 -1 2 6 
    最长子序列的和 = 11
      

  4.   

    要简单的?刚刚在另外一个帖子发的public static void func(int[] array) {
    int m = 0;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
    m = m + array[i] > 0 ? m + array[i] : 0;
    result = result > m ? result : m;
    }
    System.out.println(result);
    }
      

  5.   

    谢谢大家
    那个错误我改好了 现在是这样的package maxSub;public class Max3 {
    private static int maxSumRec(int[] a, int left, int right)
    {
    if(left == right)
    if(a[left]>0)
    return a[left];
    else
    return 0;

    int center = (left+right)/2;
    int maxLeftSum = maxSumRec(a,left,center);
    int maxRightSum = maxSumRec(a,center+1,right);

    int maxLeftBorderSum= 0, leftBorderSum = 0;
    for(int i =center;i>=left;i--)
    {
    leftBorderSum += a[i];
    if(leftBorderSum>maxLeftBorderSum)
    maxLeftBorderSum = leftBorderSum;
    }

    int maxRightBorderSum =0, rightBorderSum = 0;
    for(int i = center+1;i<=right;i++)
    {
    rightBorderSum +=a[i];
    if(rightBorderSum>maxRightBorderSum)
    maxRightBorderSum = rightBorderSum;
    }

    return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
    }

    public static int max3(int a,int b,int c)
    {
    int temp = 0;
    temp= a>b ? a:b;
    temp= temp>c ? temp :c;
    return temp;
    }

    public static void main(String[] args)
    {
    int [] a={4,-3,5,-2,-1,2,6,-2};
    System.out.println(maxSumRec(a,0,a.length-1));
    }}我主要是想知道这个程序的原理,其他简单的算法还有很多我都懂了,就是这个比较模糊。。
      

  6.   

    楼主真执着,佩服。楼主程序的算法是二分法,把数组分两半,用递归的办法,找出每一半的最大子序列的值(maxLeftSum,maxRightSum)。然后从center位置处向开始两边计算,算出包含center位置序列的最大值(maxLeftBorderSum+maxRightBorderSum)。最后比较这三个值,取最大的。