Given an array, find k increasing numbers whose sum will be maximum

#include <stdio.h>
#include <vector>
#include <numeric>
#include <iostream>

using namespace std;

typedef vector<int> Seq;

Seq increaseseqsum(int *a, int n, int k)
{
Seq r;

if(!a || !n || !k || k > n )
return r;

if(k == 1)
{
int max = *a;

for(int i = 1; i < n ; ++i)
{
if(a[i] > max)
max = a[i];
}
r.push_back(max);

return r;
}


Seq r1 = increaseseqsum(a + 1, n - 1 , k - 1);
Seq r2 = increaseseqsum(a + 1, n - 1 , k);


if(r1.empty() || r1.back() < *a)
return r2;

r1.push_back(*a);

if(r2.empty())
return r1;

int sum1 = accumulate(r1.begin(), r1.end(), 0);
int sum2 = accumulate(r2.begin(), r2.end(), 0);

if(sum1 > sum2)
return r1;

return r2;
}

int main()
{
int n, k;

scanf("%d %d", &n, &k);

int a[n];

for(int i = 0; i < n; ++i)
scanf("%d", a + i);

Seq r = increaseseqsum(a, n , k);

copy(r.begin(), r.end(), ostream_iterator<int>(cout, " "));
cout<<endl;

}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s