网站推广最有效的方法搜索风云榜百度

问题
给出一个长度为n的序列A1,A2,…,An，求最大连续和。
即：求找到1<= i <= j <=n,使得Ai+…+Aj尽量大。
以下代码以 数组A[n+1] 的值都等于下标为例
分析：
最简单的方法就是枚举每个子串，求出和最大的子串。

    int best=A[1];for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){int sum=0;for(int begin=i;begin<=j;begin++){sum+=A[begin];if(best>sum)best=sum;}}}System.out.println(best);

时间复杂度是n的三次方，只能处理小数据

下面尝试进行优化
可以考虑用前缀和来把时间复杂度优化为n的平方
因为连续子序列之和等于两个前缀和之差
求子序列的和直接用S[j]-S[i-1]即可 省去了一个循环
这里的max函数是求两个数中最大的一个，代码省略

S[0]=0;int best=0;for(int i=1;i<=n;i++){S[i]=S[i-1]+i;}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){best=max(best,S[j]-S[i-1]);}}System.out.println(best);

用分治法来处理
时间复杂度为n*logn

 static int n;static int[] A;public static void main(String[] args) {Scanner sc=new Scanner(System.in);n=sc.nextInt();A=new int[n+1];for(int i=1;i<=n;i++){A[i]=i;}int ans=split(A,1,n+1);System.out.println(ans);}//返回数组在左闭右开区间[x,y)中的最大连续和static int split(int[] A,int x,int y){int v,L,R,maxs;if(y-x==1)return A[x]; //只有一个元素，直接返回int mid=x+(y-x)/2;    //分治第一步：划分成[x,mid)和[mid,y)maxs=max(split(A,x,mid),split(A,mid,y));//分治第二步：递归求解v=0;L=A[mid-1];  //分治第三步：(合并1) 从分界点开始往左的最大连续和Lfor(int i=L;i>=x;i--){L=max(L,v+=A[i]);}v=0;R=A[mid];   //分治第三步：合并(2) 从分界点开始往右的最大连续和Rfor(int i=R;i<y;i++){R=max(R,v+=A[i]);}return max(maxs,L+R);   //把子问题的解与L和R比较}static int max(int a,int b){return a<b?b:a;}