Pagini recente » Cod sursa (job #2828352) | Cod sursa (job #1894136) | Cod sursa (job #2760658) | Cod sursa (job #3132892) | Cod sursa (job #2213432)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int length,sequence[100001],temporaryArray[100001],Solution[100001],Solution2[100001];
void LIS ()
{
int i,j;
for (i = 1; i <= length ; i++)
{
temporaryArray[i] = 1;
Solution[i] = i;
}
for (i = 2; i <= length ; i++)
for (j = 1; j <= i ; j++)
{
if (sequence[i] >sequence [j] && temporaryArray[j] + 1 > temporaryArray[i])
{
temporaryArray[i] = temporaryArray [j] + 1;
Solution[i] = j;
}
}
int maxIndex = 0;
for (i = 1; i <= length; i++)
if (temporaryArray[i] > temporaryArray[maxIndex]) maxIndex = i;
int t = maxIndex;
fout << temporaryArray[maxIndex] <<endl;
int newT = maxIndex;
i = 1;
do
{
t = newT;
Solution2[i] = sequence[t];
newT = Solution [t];
i++;
}
while (t != newT);
for (i-- ; i>=1; i--)
fout << Solution2[i]<<' ';
}
int main ()
{
fin >> length;
for (int i = 1; i <= length; i++)
fin >> sequence[i];
LIS();
return 0;
}