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 :
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 .

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 the maximum sum of sub segments

Example Input
6 -2 11 -4 13 -5 -2
Example Output
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) { *)malloc(sizeof(int)*n);
int i=0; while(n--) { scanf("%d", &[i++]); } seeq.last=i; } void
tlcs(seq &seeq) {for(int a=1; a<seeq.last; a++) { if([a]<[a-1
][a])[a][a-1][a]; if
([a]>max1)[a]; } }int main() { int n; seq seeq; scanf(
"%d", &n); head(n, seeq);[0]; tlcs(seeq); if(max1<0)max1=0;
printf("%d\n",max1); return 0; }

Daily Recommendation
views 214
views 191
views 181