顺序表应用8：最大子段和之动态规划法

短命女 2022-09-26 01:58 107阅读 0赞

### 顺序表应用8：最大子段和之动态规划法 ###

Time Limit: 5MS Memory Limit: 500KB

[Submit][] [Statistic][]

#### Problem Description ####

给定n(1<=n<=100000)个整数（可能为负数）组成的序列a\[1\],a\[2\],a\[3\],…,a\[n\],求该序列如a\[i\]+a\[i+1\]+…+a\[j\]的子段和的最大值。当所给的整数均为[负数][Link 1]时定义子段和为0，依此定义，所求的最优值为： Max\{0,a\[i\]+a\[i+1\]+…+a\[j\]\},1<=i<=j<=n。 例如，当（a\[1\],a\[2\],a\[3\],a\[4\],a\[5\],a\[6\]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

注意：本题目要求用动态规划法求解，只需要输出最大子段和的值。

#### Input ####

第一行输入整数n(1<=n<=100000)，表示整数序列中的数据元素个数；

第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。

#### Output ####

输出所求的最大子段和

#### Example Input ####

6
    -2 11 -4 13 -5 -2

#### Example Output ####

#### `#include<stdio.h> #include<algorithm> #define MAXSIZE 100000 typedef struct { int *elem; int length; int listsize; }qlist; //初始化顺序表 void Initlist(qlist &L) { L.elem=new int[MAXSIZE]; L.length=0; L.listsize=MAXSIZE; } //创建顺序表 void Creatlist(qlist &L,int n) { for(int i=0;i<n;i++) { scanf("%d",&L.elem[i]); } L.length=n; } //计算局部子段最大和 void Sumlist(qlist &L) { int max=0; int maxsum=0; for(int i=0;i<L.length;i++) { maxsum+=L.elem[i]; if(maxsum<0) { maxsum=0; } if(maxsum>max) { max=maxsum; } } printf("%d\n",max); } int main() { int n; scanf("%d",&n); qlist L; Initlist(L); Creatlist(L,n); Sumlist(L); return 0; }`         ####

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1823/pid/3665.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1823/pid/3665.html
[Link 1]: http://baike.baidu.com/view/71543.htm