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