Largest sum issue

[lastchance]

mbozzi wrote:

nth_element might be better than partial_sort

Yes, you are right!

I hadn't realised at the time that it effects a partition, not just places the nth element itself.

It's a seemingly under-used (at least by me) part of <algorithm>.

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

int sumBestTwo( vector<int> &V )
{
   nth_element( V.begin(), V.begin() + 1, V.end(), greater<int>() );
   return V[0] + V[1];
}

int main()
{
   vector< vector<int> > tests = { { 122, 117, 28, 9, 1, 27, 6, 111, 322 }, { 5, 9, 7, 11 } };
   for ( auto &V : tests ) cout << sumBestTwo( V ) << '\n';
}