最长递增(减)子序列

// runtime: 4ms
// space: 504K
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 25;

int arr[MAX];
int dp[MAX]; // dp[i]定义为：以arr[i]为结尾的最长递增(减)子序列。

int MaxDecSubsequence(int k) {
    int answer = 0;
    for (int i = 0; i < k; ++i) {
        dp[i] = 1;

        for (int j = 0; j < i; ++j) {
            if (arr[i] <= arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        answer = max(answer, dp[i]);
    }
    return answer;
}

int main() {
    int k;
    while (scanf("%d", &k) != EOF) {
        for (int i = 0; i < k; ++i) {
            scanf("%d", &arr[i]);
        }

        printf("%d\n", MaxDecSubsequence(k));
    }
    return 0;
}

很经典的dp问题。