c語言，最長上升子序列數，C語言，最長上升子序列數,,

1樓：匿名使用者

最長上升子序列（lis）

問題描述：設現在有一串序列，要求找出它的一串子序列，這串子序列可以不連續，但必須滿足它是嚴格的單調遞増的且為最長的。把這個長度輸出。

示例：1 7 3 5 9 4 8 結果為4題例：參看poj 2533

解法：1. dp之o(n2)演算法：

先按dp的思想來分析一下，要想求n個數的最長上升子序列，設有資料陣列data[n]和狀態陣列dp[n]，則對其尾元素data[n]來說，它的最長上升子序列就是它自己，即dp[n]=1，而當把它的前一個元素data[n-1]考慮進來時，如果data[n-1]data[n]那麼這個長度仍會是1。當把這個思想一般化的時候，對於任意一個元素data[k]來說，我們需要找出在data[k]以後的元素中比data[k]大，並且最長的一個序列做為它的後繼。這樣dp[k]就可以寫成dp[k+1]+1。

現在我們定義一個量dp[k]=m，它代表著到第k個元素為止（可以包含k也可以不包含k），它的最長上升序列的長度為m。仔細體會dp[k]=m的意義，這裡面的k是可包括在內，也可以不包括在內的（與之前的最大子序列和不同）。要想確定這個m的值，就必須找到一個在第k個元素之前的一個元素的值小於data[k]的值，並且那個元素所對應的dp值是找到的滿足第一個條件前提下dp值最大的一個。

這就意味著我們需要內層遍歷之前算出來的dp值，所以需要兩層迴圈來實現這個演算法。這樣我們就可以總結出狀態轉移方程為dp[k]=max(dp[i](1<=i<=k&&a[i]

const int inf = -0x3fffffff;

int main(void)

,dp[20]=;

len = sizeof(data)/sizeof(int);

res = max = inf;

for(i=1;idata[j]&&max

dp[i]=max+1;

if(res

res = dp[i];

}printf("%d\n",res);

return 0;}

2樓：

#include

main()

printf("%d",count);

system("pause");

} 這個是非遞減的，不是遞增的，如果要遞增的改一點就行了

誰幫忙做個c語言題目：最長上升下降子序列 **等答案！！！

3樓：

你是理工的吧

#include

const int max=105;

int down[max],up[max];

int h[max],n;

void get_up()

up[i]=tmp;}}

void get_down()

down[i]=tmp;}}

int main()

printf("%d\n",n-max);

}return 0;}

一道acm的題目，求用c語言遞迴編寫的演算法，非常感謝啊!!!：求上升子序列和的最大值

4樓：飛向夢魘天空

您好！這是杭電acm的第1087題，答案如下：

#include

__int64 a[10009],sum[10009],maxsum,max;

int main()

sum[i]=maxsum+a[i];

}max=sum[0];

for(i=1;i

if(max

max=sum[i];

printf("%i64d\n",max);

}return 0;

}希望對您有幫助！

c語言，最長上升子序列數，C語言，最長上升子序列數,,

C語言最垃圾問題請指教，C語言最垃圾問題請指教

糾正 c語言程式設計有一分數序列

C語言程式設計3題求用最簡單的定義語言來寫includestdio h這種的

其他用戶還看了：

c語言，最長上升子序列數，C語言，最長上升子序列數,,

C語言最垃圾問題請指教，C語言最垃圾問題 請指教

糾正 c語言程式設計 有一分數序列

C語言程式設計3題求用最簡單的定義語言來寫includestdio h這種的

其他用戶還看了：

C語言最垃圾問題請指教，C語言最垃圾問題請指教

糾正 c語言程式設計有一分數序列