7-1 單調遞增最長子序列設計一個O(n2)時間的算法，找出由n個數組成的序列的最長單調遞增子序列。輸入格式:輸入有兩行： 第一行：n，代表要輸入的數列的個數 第二行：n個數，數字之間用空格格開輸出格式:最長單調遞增子序列的長度輸入樣例:在這里給出一組輸入。例如：51 3 5 2 9輸出樣例:在這里給出相應的輸出。例如：4
2 回答
函數式編程
TA貢獻1807條經驗 獲得超9個贊
#include <stdio.h>
#define MAX_N 1000
int dp[MAX_N], a[MAX_N];
int n;
void input()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
}
int max_(int a, int b)
{
return a > b ? a : b;
}
void slove()
{
//注意要res保存結果
int res = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < i; ++j)
if(a[j] < a[i])
dp[i] = max_(dp[i], dp[j] + 1);
res = max_(dp[i], res);
}
printf("%d\n", res + 1);
}
int main()
{
input();
slove();
return 0;
}- 2 回答
- 0 關注
- 1280 瀏覽
添加回答
舉報
0/150
提交
取消