// 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问题。