C++语言编程 最大子段和

Question

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0。要求算法的时间复杂度为O(n)。

输入格式:
输入有两行： 第一行是n值（1<=n<=10000)； 第二行是n个整数。

输出格式:
输出最大子段和。

输入样例:
在这里给出一组输入。例如：

6
-2 11 -4 13 -5 -2
输出样例:
在这里给出相应的输出。例如：

20

#include
using namespace std ; ………………
………………………………

Answer 1

也可以用DP #include&nbsp;<stdlib.h> #include<stdio.h> int&nbsp;main() { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;a[100]; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;b[100]; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;max; &nbsp;&nbsp;&nbsp;&nbsp;scanf("%d",&count); &nbsp;&nbsp;&nbsp;&nbsp;for(i=0;&nbsp;i<count;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf("%d",&a[i]); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;b[0]=a[0]; &nbsp;&nbsp;&nbsp;&nbsp;max=b[0]; &nbsp;&nbsp;&nbsp;&nbsp;for(i=1;&nbsp;i<count;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(b[i-1]>0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[i]=b[i-1]+a[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[i]=a[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(b[i]>max) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max=b[i]; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;printf("%d\n",max); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; }

Answer 2

&nbsp;#include&nbsp;<cstdio> typedef&nbsp;long&nbsp;long&nbsp;LL; int&nbsp;main(int&nbsp;argc,&nbsp;char&nbsp;const&nbsp;*argv[]) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n; &nbsp;&nbsp;&nbsp;&nbsp;scanf("%d",&nbsp;&n); &nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;t,&nbsp;tmp; &nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;ans&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;n;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf("%lld",&nbsp;&t); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(i&nbsp;>&nbsp;0&nbsp;&&&nbsp;tmp&nbsp;>&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;+=&nbsp;tmp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(ans&nbsp;<&nbsp;t) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;t; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp&nbsp;=&nbsp;t; &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;printf("%lld\n",&nbsp;ans); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; }