Problem Description
given n(1<=n<=100000) Integers （ It may be negative ） Composed sequence a[1],a[2],a[3],…,a[n], Find the sequence as follows a[i]+a[i+1]+…+a[j] The maximum value of the sum of the subsegments of . When all the given integers are negative, define sub segments and 0, According to this definition , The optimal value obtained is ：
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n.
for example , When （a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2) Time , The maximum sum of sub segments is 20.
be careful ： Dynamic programming is required to solve this problem , You only need to output the value of the sum of the largest sub segments .
Input
Enter an integer on the first line n(1<=n<=100000), Represents the number of data elements in an integer sequence ;
Enter the second line in turn n Integers , Corresponding to the value of each data element stored in the sequence table .
Output
Output the maximum sum of sub segments
Example Input
6 -2 11 -4 13 -5 -2
Example Output
20
Hint
Author
ps:
Dynamic programming is poor , Still need to continue to refuel !
#include <stdio.h> #include <stdlib.h> #include <string.h>
#include<bits/stdc++.h> #include <iostream> #include <algorithm> #define maxn
10100 using namespace std; int max1=0; typedef struct list { int *data; int
last; }seq;void head(int n, seq &seeq) { seeq.data=(int *)malloc(sizeof(int)*n);
int i=0; while(n--) { scanf("%d", &seeq.data[i++]); } seeq.last=i; } void
tlcs(seq &seeq) {for(int a=1; a<seeq.last; a++) { if(seeq.data[a]<seeq.data[a-1
]+seeq.data[a]) seeq.data[a]=seeq.data[a-1]+seeq.data[a]; if
(seeq.data[a]>max1)max1=seeq.data[a]; } }int main() { int n; seq seeq; scanf(
"%d", &n); head(n, seeq); max1=seeq.data[0]; tlcs(seeq); if(max1<0)max1=0;
printf("%d\n",max1); return 0; }
Technology