Cod sursa(job #2167227)

Utilizator alex02Grigore Alexandru alex02 Data 13 martie 2018 20:42:59
Problema Subsir crescator maximal Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
/* 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;
}