This question has already been answered:

Hello everyone, there is such a task, it gives me a time limit. The task limit is 2 seconds.

Here is the task:

From the input device comes a sequence of integers. The length of the sequence is unknown. It is required to find the maximum amount of successive elements of a sequence. Elements of the sequence to read to the end of the input.

Input Format

A sequence of integers separated by one or more spaces or a newline.

Output format

The required maximum amount in one line.

Sample input

1 2 -5 3 2 -1 5 -10 3 2

Sample output

9

And here is my code:

#include <bits/stdc++.h> using namespace std; int main(){ vector<int>ciss; int cis,sum=0,ii=0,summax=0; while(cin>>cis) ciss.push_back(cis); for(int i=0;i<ciss.size();i++) { sum=0; for(int j=i;j<ciss.size();j++) { sum+=ciss[j]; if(sum>summax) summax=sum; } } cout<<summax<<endl; return 0; }

How to avoid the time limit in this problem?

Reported as a duplicate by members pavel , Mike , jfs , Abyx c ++ Apr 17 '17 at 12:52 .

A similar question was asked earlier and an answer has already been received. If the answers provided are not exhaustive, please ask a new question .

  • Probably, we must get away from stupid busting and come up with something more meaningful ... - Akina
  • @Akina oh well)) - futuretourist
  • one
    ru.stackoverflow.com/questions/129360/… - Akina
  • @Akina would immediately have been noted as a duplicate. - pavel
  • Far to you before the "tourist". The answer has already been given above, but the task is from the field of dynamic programming, therefore I recommend to derive a recurrent formula for a deep understanding of the problem. - Victor Khovanskiy

1 answer 1

It seems to be the way O(n) gives - we accumulate partial sums and look for the maximum difference of the largest on the right with the smallest on the left:

 int main() { int n, sum = 0, min = 0, max = 0; while(cin >> n) { sum += n; if (sum < min) min = sum; else if (sum - min > max) max = sum - min; } cout << max << endl; }