題目描述

一個數列ai如果滿足條件a1?<?a2?< ... <?aN，那么它是一個有序的上升數列。我們取數列(a1,?a2, ...,?aN)的任一子序列(ai1,?ai2, ...,?aiK)使得1 <=?i1?<i2?< ... <?iK?<=?N。例如，數列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列，像(1, 7)，?(3, 4, 8)和許多其他的子序列。在所有的子序列中，最長的上升子序列的長度是4，如(1, 3, 5, 8)。

????現在你要寫一個程序，從給出的數列中找到它的最長上升子序列。

輸入

輸入包含兩行，第一行只有一個整數N（1 <= N <= 1000），表示數列的長度。

第二行有N個自然數ai，0 <= ai?<= 10000，兩個數之間用空格隔開。

輸出

輸出只有一行，包含一個整數，表示最長上升子序列的長度。

樣例輸入

7 1 7 3 5 9 4 8

樣例輸出

4

AC：

#include <iostream> #include <algorithm> using namespace std;const int maxn = 1005; int A[maxn], dp[maxn]; int n;int main() {scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &A[i]);}for(int i = 1; i <= n; i++){dp[i] = 1;for(int j = 1; j < i; j++){if(A[i] >= A[j] && dp[j] + 1 > dp[i] ){dp[i] = dp[j] + 1;}}}int ans = 0;for(int i = 1; i <= n; i++){ans = max(ans,dp[i]);}printf("%d\n", ans);return 0; }

?

總結

以上是生活随笔為你收集整理的Codeup墓地-问题 A: 最长上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。