Pagini recente » Istoria paginii utilizator/stomitu | Istoria paginii runda/asda2dasd/clasament | Rating Cristin Iosif (cristin.iosif) | Rating Farcasiu Razvan (Farcasiu) | Cod sursa (job #2750464)
#include <fstream>
#include <stack>
#define MAX 100005
#define INF 2147483647
using namespace std;
ifstream fin ("scmax.in");
ofstream fout("scmax.out");
int n;
int arr[MAX];
int SCM[MAX];
int answer;
int max(int x, int y)
{
return x > y ? x : y;
}
void read()
{
fin >> n;
for (int i = 0; i < n; ++ i)
fin >> arr[i];
}
void solve()
{
SCM[0] = 1;
for (int i = 1; i < n; ++ i)
{
int maxim = 1;
for (int j = 0; j < i; ++ j)
if (arr[j] < arr[i])
maxim = max(SCM[j] + 1, maxim);
SCM[i] = maxim;
}
answer = 1;
for (int i = 0; i < n; ++ i)
answer = max(answer, SCM[i]);
}
void print()
{
int lastAnswer = INF;
stack<int> result;
fout << answer << endl;
for (int i = n - 1; i >= 0; -- i)
{
if (answer == SCM[i] && arr[i] < lastAnswer)
{
result.push(arr[i]);
answer -= 1;
lastAnswer = arr[i];
}
}
while (!result.empty())
{
fout << result.top() << ' ';
result.pop();
}
}
int main() {
read();
solve();
print();
return 0;
}