本文實例展示了C語言實現最長遞增子序列問題的解決方法。分享給大家供大家參考。具體方法如下：
問題描述：
給定一個序列，找出其最長遞增子序列長度。
比如 輸入 1 3 7 5
輸出 3
算法解決思路：
利用動態(tài)規(guī)劃的思想，以序列的每個點最為最右端，找出每個點作為最右端時的子序列長度的最大值，即問題的求解。因此，在計算前面的每個點的時候，將其結果保存下來，后面的點與前面的點的數值進行比較，如果大，則在其長度基礎上加1，并且找出所有可能情況下最長的保存為當前點的長度。形成遞歸。
具體實現代碼如下：
#include "stdio.h"#include "stdlib.h"#define MAXDATA 10000int main(){ int data[MAXDATA]; /*數據序列*/ int lgs[MAXDATA]; /*最長子序列長度*/ int n,temp,k; /*n 序列長度 temp 子序列長度中間變量 */ scanf("%d",&n); if(n>10000){ return 0; } for(int i=0;i<n;i++){ scanf("%d",&data[i]); } for(int i=0;i<MAXDATA;i++){ lgs[i]=1; /*給每一個序列點作為右端時的最大序列長度為1*/ } for(int i=1;i<n;i++){ temp=1; for(int j=0;j<i;j++){ /*與其前面的每一個進行比較*/ if(data[i]>data[j]){ /*如果數據比前面的某一個的值大*/ if(lgs[i]+lgs[j]>temp){ /*找出該點的最大子序列長度*/ temp=lgs[i]+lgs[j]; } } } lgs[i]=temp; } temp=lgs[0]; for(int i=1;i<n;i++){ if(lgs[i]>temp){ temp=lgs[i]; } } printf("%d",temp); system("pause");}希望本文所述對大家C程序算法設計的學習有所幫助。
新聞熱點
疑難解答
圖片精選
