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
©2020 ioDraw All rights reserved
python gui Interface examples -Python GUI Programming complete example vue element-ui Drop down menu with search algorithm : Longest common subsequence ( Output all longest common subsequences ) First knowledge Mongdb Data query ( three ) The problem of time type conversion “2021-01-20T10:09:11Z” Morphological processing gradient , Top hat , Black hat mean value - Implementation and application of variance model _python_ Data analysis _9 Wechat small program student course selection system app Design CCF A series of questions --2016 year 4 Month 1 Calculation of break point laravel The first mock exam is based on the "one to many" model. with,has,wherehas