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的啊。。
谢谢朋友了!
第三个参数??
return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
maxRightSum是8,所以你得到12了,maxRightBorderSum才是7。
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
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);
}
那个错误我改好了 现在是这样的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));
}}我主要是想知道这个程序的原理,其他简单的算法还有很多我都懂了,就是这个比较模糊。。