7-1 單調(diào)遞增最長(zhǎng)子序列設(shè)計(jì)一個(gè)O(n2)時(shí)間的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列。輸入格式:輸入有兩行： 第一行：n，代表要輸入的數(shù)列的個(gè)數(shù) 第二行：n個(gè)數(shù)，數(shù)字之間用空格格開(kāi)輸出格式:最長(zhǎng)單調(diào)遞增子序列的長(zhǎng)度輸入樣例:在這里給出一組輸入。例如：51 3 5 2 9輸出樣例:在這里給出相應(yīng)的輸出。例如：4
2 回答
函數(shù)式編程
TA貢獻(xiàn)1807條經(jīng)驗(yàn) 獲得超9個(gè)贊
#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保存結(jié)果
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 關(guān)注
- 1248 瀏覽
添加回答
舉報(bào)
0/150
提交
取消