Pagini recente » Cod sursa (job #779704) | Cod sursa (job #1150399) | Cod sursa (job #1884399) | Cod sursa (job #1960705) | Cod sursa (job #2167227)
/* Dynamic Programming implementation of Maximum Sum Increasing
Subsequence (MSIS) problem */
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
void maxSumIS( int arr[], int n )
{
int i, j, msis[n];
for ( i = 0; i < n; i++ )
{
msis[i] = arr[i];
}
int maxi=0,vect_aux[100000],vect[10000],nr_elm_aux=0,nr_elm=0;
for ( i = 1; i < n; i++ )
{
nr_elm_aux=0;
for ( j = 0; j < i; j++ )
{
if ( arr[i] > arr[j] && msis[i] < msis[j] + arr[i])
{
msis[i] = msis[j] + arr[i];
vect_aux[nr_elm_aux++]=arr[j];
}
}
vect_aux[nr_elm_aux++]=arr[i];
if(maxi<msis[i])
{
maxi=msis[i];
for(int k=0; k<nr_elm_aux; k++)
vect[k]=vect_aux[k];
nr_elm=nr_elm_aux;
}
}
///AFISARE
sort(vect,vect+nr_elm);
g<<nr_elm<<'\n';
for(int i=0; i<nr_elm; i++)
g<<vect[i]<<" ";
}
int main()
{
int arr[100000],n;
f>>n;
for(int i=0; i<n; i++)
{
f>>arr[i];
}
maxSumIS( arr, n );
return 0;
}