黑马程序员技术交流社区
标题:
用“在线处理”和“分而治之”的思想求“最大子列和”...
[打印本页]
作者:
as604049322
时间:
2014-12-13 19:53
标题:
用“在线处理”和“分而治之”的思想求“最大子列和”...
今天晚上尝试用“分而治之”的思想解决求“最大子列和”问题,结果居然成功了,自己都不敢相信自己居然写出了下面的递归代码
public static int[] getMaxSubsequenceIndex(int[] arr, int start, int end){
if(start==end)
return new int[]{start,end};
int mid=(start+end)/2;
return binarySearchMaxSubseq(arr,getMaxSubsequenceIndex(arr,start,mid),getMaxSubsequenceIndex(arr,mid+1,end));
}
复制代码
下面是全部代码:
/*
给定K个整数组成的序列{ N1, N2, ..., NK },“连续子列”被定义为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。
“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },
其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和,以及和最大的子列高低位角标
输入格式:
输入第1行给出正整数 K (<= 100000);第2行给出K个整数,其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。
输入样例:
6
-2 11 -4 13 -5 -2
输出样例:
20 1 3
*/
import java.util.Scanner;
class GetMaxSubsequence
{
public static void main(String[] args)
{/*
Scanner scanner =new Scanner(System.in);
System.out.println("请输入一串整数序列,每个整数以空格隔开\n输入样例:-2 11 -4 13 -5 -2");
String str=scanner.nextLine();
String[] sequence=str.split(" ");
int[] arr=new int[sequence.length];
for(int i=0;i<arr.length;i++) {
arr[i]=new Integer(sequence[i]);
//System.out.println(arr[i]);
}*/
int[] temp={2,7,-8,2,16,-5,-50,-20,-10,-8,-6};
System.out.println(getMaxSubsequenceSum(temp));
int[] maxIndex=getMaxSubsequenceIndex(temp,0,temp.length-1);
System.out.println(maxIndex[0]+"..."+maxIndex[1]);
}
/*该算法的思想是在线处理*/
public static int getMaxSubsequenceSum(int[] arr){
int ThisSum=0,MaxSum=0,left=0,right=-1,realleft=-1;
for(int i=0;i<arr.length;i++){
ThisSum+=arr[i];
if(ThisSum>MaxSum){
MaxSum=ThisSum;
if(i>=left){
right=i;
realleft=left;
}
}
else if(ThisSum<0){
ThisSum=0;
left=i+1;
}
}
System.out.println("i:"+realleft+",j:"+right);
return MaxSum;
}
private static int[] binarySearchMaxSubseq(int[] arr,int[] i,int[] j){
int sum1=0,sum2=0,sum3=0,max;
int[] result=new int[2];
for(int k=i[0];k<=i[1];k++)
sum1+=arr[k];
for(int k=j[0];k<=j[1];k++)
sum2+=arr[k];
if(sum1>=sum2) max=sum1;
else max=sum2;
for(int k=i[0];k<=j[1];k++)
sum3+=arr[k];
if(sum3>max) max=sum3;
if(max==sum1){
result[0]=i[0];
result[1]=i[1];
}else if(max==sum2){
result[0]=j[0];
result[1]=j[1];
}else if(max==sum3){
result[0]=i[0];
result[1]=j[1];
}
System.out.println("范围:"+i[0]+"~"+j[1]+",最大子序列范围:"+result[0]+"~"+result[1]);
return result;
}
/*
该算法为“分而治之”,即将一个大问题分解成若干小问题
*/
public static int[] getMaxSubsequenceIndex(int[] arr, int start, int end){
if(start==end)
return new int[]{start,end};
int mid=(start+end)/2;
return binarySearchMaxSubseq(arr,getMaxSubsequenceIndex(arr,start,mid),getMaxSubsequenceIndex(arr,mid+1,end));
}
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2