### how to find the highest sum of a subsequence

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.
Last edited on
You could start by making a list of steps to be performed
- 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.
http://www.cplusplus.com/reference/numeric/partial_sum/

(Although, actually, you could do it in a single pass without using that.)
Last edited on
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.
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 :)
Last edited on
 ``12345678910111213141516171819202122`` ``````#include #include using namespace std; int bestSubsequenceSum( const vector &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 A = { -10, 23, 4, 91, 3, 18, -67, 9, 12, 5 }; cout << bestSubsequenceSum( A ); }``````

Topic archived. No new replies allowed.