題目:輸入n個數,求最大的連續子段和,並輸出子段的起點下標和終點下標; 思路:分治法; 代碼如下: ...
題目:輸入n個數,求最大的連續子段和,並輸出子段的起點下標和終點下標;
思路:分治法;
代碼如下:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <map> #define N 1000005 using namespace std; int a[1005]; int calc(int s,int e,int &l,int &r) { int l1,l2,l3,r1,r2,r3; ///if(s==e) return a[s]>0?a[s]:0; if(s==e) { if(a[s]>0) { l=s; r=s; return a[s]; } else return 0; } int mid=(s+e)>>1; int sum1=calc(s,mid,l1,r1); int sum2=calc(mid+1,e,l2,r2); int sl=0,sr=0,t=0; for(int i=mid; i>=s; i--) { t+=a[i]; if(sl<t) sl=t,l3=i; } t=0; for(int i=mid+1; i<=e; i++) { t+=a[i]; if(sr<t) sr=t,r=i,r3=i; } int ss=sl+sr; l=l3,r=r3; if(ss<=sum1) ss=sum1,l=l1,r=r1; if(ss<=sum2) ss=sum2,l=l2,r=r2; return ss; } int main() { int n; while(1) { printf("輸入數列長度:"); scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); int l=1,r=1; int sum=calc(1,n,l,r); if(sum>0) { cout<<"最大子段和:"<<sum<<endl; cout<<"起點和終點:"<<l<<" "<<r<<endl; } else { cout<<"最大子段和:"<<sum<<endl; cout<<"無起點和終點!"<<endl; } cout<<endl; } return 0; }
運行截圖: