Cod sursa(job #2985790)

Utilizator highonrocketfuelOverweight Raccoon highonrocketfuel Data 27 februarie 2023 08:48:29
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <algorithm>
#include <fstream>
#include <iostream>

#define r inFile
#define w outFile

const int NMAX = 1e5;

int n;
int a[1 + NMAX];

int prev[1 + NMAX];
int dp[1 + NMAX];

void printPath(int i, std::ostream &str) {
  if (i == 0) {
    return;
  }

  printPath(prev[i], str);
  str << a[i] << ' ';
}

int main() {
  std::ifstream inFile("scmax.in");
  std::ofstream outFile("scmax.out");

  r >> n;

  for (int i = 1; i <= n; ++i) {
    r >> a[i];
  }

  // dp[i] - longest str. increasing subarray ending at position i

  dp[1] = 1;
  prev[1] = 0;
  for (int i = 2; i <= n; ++i) {
    dp[i] = 1;
    for (int j = 1; j <= n; ++j) {
      if (a[j] < a[i] && dp[j] >= dp[i]) {
        dp[i] = 1 + dp[j];
        prev[i] = j;
      }
    }
  }

  int ans = -1;
  for (int i = 1; i <= n; ++i) {
    if (dp[i] > dp[ans]) {
      ans = i;
    }
  }

  w << dp[ans] << '\n';

  printPath(ans, w);

  return 0;
}