how to find the highest sum of a subsequence

[algmaster]

How to write a program in C++ to find the highest sum of subsequence elements of a given sequence? At the input, the user gives the length of the sequence and then the individual elements of this sequence. The elements of the sequence are integers. For example -10 23 4 91 3 18 -67 9 12 5. In this case the highest sum is 139. I would be grateful for any advice or tips.

[salem c]

You could start by making a list of steps to be performed
- read integer
- add to total
- compare running total to max total

You need to start doing this yourself, not just be able to copy/paste from your tutor to this website.

[lastchance]

http://www.cplusplus.com/reference/numeric/partial_sum/

(Although, actually, you could do it in a single pass without using that.)

[keskiverto]

You are not consistent. Do you want
"highest subsequence"
or
"highest sum of subsequence"?

They are related, but one requires less book-keeping than the other.

[algmaster]

The task is solved already. If anyone is interested in the solution I can help on PM. My hour rates are not higher than salem's ones :)

[lastchance]

#include <iostream>
#include <vector>
using namespace std;

int bestSubsequenceSum( const vector<int> &A )
{
   int sum = 0, lowsum = 0, best = 0;
   for ( int e : A )
   {
      sum += e;
      if ( sum < lowsum ) lowsum = sum;
      if ( sum - lowsum > best ) best = sum - lowsum;
   }
   return best;
}


int main()
{
   vector<int> A = { -10, 23, 4, 91, 3, 18, -67, 9, 12, 5 };
   cout << bestSubsequenceSum( A );
}