Pagini recente » Cod sursa (job #1795324) | Cod sursa (job #3151360) | Cod sursa (job #319132) | Cod sursa (job #1411781) | Cod sursa (job #2609669)
#include <fstream>
#include <vector>
using namespace std;
const char inputFile[] = "scmax.in";
const char outputFile[] = "scmax.out";
ifstream in(inputFile);
ofstream out(outputFile);
unsigned N, rez, pos;
vector<unsigned> v, dp;
void type(unsigned pos, unsigned rez)
{
if(!rez)
return;
if(dp[pos] == rez)
{
if(pos > 0)
type(pos - 1, rez - 1);
out << v[pos] << ' ';
}
else type(pos - 1, rez);
}
int main(void)
{
in >> N;
v.resize(N);
dp.resize(N);
for(unsigned i = 0; i < N; ++i)
{
in >> v[i];
dp[i] = 1;
for(unsigned j = 0; j < i; ++j)
if(v[j] < v[i] && dp[j] + 1 > dp[i])
{
bool ok = (dp[j] == rez);
dp[i] = dp[j] + 1;
if(dp[i] > rez)
{
rez = dp[i];
pos = i;
}
if(ok)
goto end_loop;
}
end_loop:
;
}
out << rez << endl;
type(pos, rez);
return 0;
}