Algorithm/longest-decreasing-subsequence/main.cc

#include <iostream>
using namespace std;
#define MAXN 10005
#define M 200
int dp[MAXN];
int obstacle[M];
int longest_decreasing_subsequence(int n) {
  int maximun = 0;
  for (int i = 0; i < n; i++) {
    dp[i]++;
    for (int j = 0; j < i; j++) {
      if (obstacle[j] > obstacle[i]) // 最大上升为 `obstacle[j] < obstacle[i]`
        dp[i] = max(dp[i], dp[j] + 1);
    }
    if (dp[i] > maximun)
      maximun = dp[i];
  }
  return maximun;
}
int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> obstacle[i];
  }
  int value = longest_decreasing_subsequence(N);
  cout << value << endl;
}