Pagini recente » Cod sursa (job #204437) | Monitorul de evaluare | Cod sursa (job #1349684) | Cod sursa (job #3324708) | Cod sursa (job #3315327)
#include <fstream>
#define NMAX 100002
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int i, j, n, a[NMAX];
int maxim, pozmax;
int dp[NMAX]; //dp[i] = lg maxima a unui subsir care incepe la pozitia i
int urmatorul[NMAX]; //pentru afisare. daca urmatorul[i] = 0 atunci sunt la cel mai mare element din acel subsir
int main()
{
fin>>n;
for(i = 1; i <= n; i++)
fin>>a[i];
dp[n] = 1;
for(i = n - 1; i > 0; i--)
{
maxim = 0;
for(j = i + 1; j <= n; j++)
if(a[i] < a[j]) //conditie subsir crescator
if(maxim < dp[j])
{
maxim = dp[j];
urmatorul[i] = j;
}
dp[i] = maxim + 1; //chiar si daca sunt in cazul incare nu pot atasa a[i] la un subsir, maxim + 1 = 1 deci voi incepe un subsir pe acea pozitie
}
//caut cel mai lung subsir
for(i = 1, maxim = 0; i <= n; i++) //voi refolosi variabila maxim (dar nu pentru acelasi scop)
if(maxim < dp[i])
{
maxim = dp[i];
pozmax = i;
}
fout<<maxim<<'\n'; //lungime subsir maxim
while(pozmax)
{
fout<<pozmax<<' ';
pozmax = urmatorul[pozmax];
}
return 0;
}