Description
一个整数序列,选出其中连续且非空的一段使得这段和最大。注意当题目要求输入输出的数据量很大时,尽量使用scanf和printf。 c++提供的cin和cout速度比较慢,有可能在读取数据和输出数据时导致超时。
输入格式
第一行是一个正整数N,表示了序列的长度(0=<N<=200000)。 第二行包含N个绝对值不大于10000的整数ai。
输出格式
一个整数,为最大的子段和。子段的最小长度为1。数据确保结果在类型int范围内。
输入样例
7 2 -4 3 -1 2 -4 3
输出样例
4
提示
【样例说明】 2,-4,3,-1,2,-4,3中,最大的子段和为4,该子段为第三元素至第五元素,即3,-1,2。
分治法
1 #include<stdio.h> 2 #define MAX 100 3 int maxsub(int left,int right); 4 int a[MAX]; 5 int main() 6 { 7 int i,count; 8 scanf("%d",&count); 9 for(i=0;i<count;i++) 10 scanf("%d",&a[i]); 11 printf("%d\n",maxsub(0,count-1)); 12 return 0; 13 } 14 int maxsub(int left,int right) 15 { 16 int center,i,sum,left_sum,right_sum,left_max,right_max; 17 center=(left+right)>>1; 18 if(left==right) 19 return a[left]>0?a[left]:0; 20 else 21 { 22 left_sum=maxsub(left,center); 23 right_sum=maxsub(center+1,right); 24 sum=0; 25 left_max=0; 26 for(i=center;i>=left;i--) 27 { 28 sum+=a[i]; 29 if(sum>left_max) 30 left_max=sum; 31 } 32 sum=0; 33 right_max=0; 34 for(i=center+1;i<=right;i++) 35 { 36 sum+=a[i]; 37 if(sum>right_max) 38 right_max=sum; 39 } 40 sum=right_max+left_max; 41 if(sum<left_sum) 42 sum=left_sum; 43 if(sum<right_sum) 44 sum=right_sum; 45 } 46 return sum; 47 }
递推法
1 #include <stdlib.h> 2 #include<stdio.h> 3 int main() 4 { 5 int count; 6 int a[100]; 7 int b[100]; 8 int i; 9 int max; 10 scanf("%d",&count); 11 for(i=0; i<count; i++) 12 { 13 scanf("%d",&a[i]); 14 } 15 b[0]=a[0]; 16 max=b[0]; 17 for(i=1; i<count; i++) 18 { 19 if(b[i-1]>0) 20 b[i]=b[i-1]+a[i]; 21 else 22 b[i]=a[i]; 23 if(b[i]>max) 24 max=b[i]; 25 } 26 printf("%d\n",max); 27 return 0; 28 }
标签:count,right,最大,子段,int,max,sum,18708,left From: https://www.cnblogs.com/lw-sin/p/16902787.html