C++

Forum

 
how to find the highest sum of a subsequence

algmaster (13)
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
salem c (3700)
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 (6980)
http://www.cplusplus.com/reference/numeric/partial_sum/

(Although, actually, you could do it in a single pass without using that.)
Last edited on
keskiverto (10402)
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 (13)
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
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#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 );
}

Topic archived. No new replies allowed.