Cod sursa(job #2684129)

Utilizator abcabc123abc abc abcabc123 Data 12 decembrie 2020 22:11:34
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int n, a[100001], dp[100001], r[100001], ma, pozma, k;

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> a[i];
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++)
      if (a[i] > a[j] and dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        if (ma < dp[i]) {
          ma = dp[i];
          pozma = i;
        }
      }
    if (dp[i] == 0)
      dp[i] = 1;
  }
  r[++k] = pozma;
  for (int i = pozma - 1; i >= 1; i--)
    if (dp[pozma] - 1 == dp[i] and a[pozma] > a[i]) {
      pozma = i;
      r[++k] = pozma;
    }
  fout << ma << '\n';
  for (int i = k; i >= 1; i--)
    fout << a[r[i]] << ' ';
  return 0;
}