C語言實現(xiàn)最長遞增子序列問題的解決方法
更新時間：2014年09月16日 15:15:16 投稿：shichen2014
這篇文章主要介紹了C語言實現(xiàn)最長遞增子序列問題的解決方法,采用遞歸的方法解決該問題,是非常經(jīng)典的一類算法,需要的朋友可以參考下
本文實例展示了C語言實現(xiàn)最長遞增子序列問題的解決方法。分享給大家供大家參考。具體方法如下：
問題描述：
給定一個序列，找出其最長遞增子序列長度。
比如 輸入 1 3 7 5
輸出 3
算法解決思路：
利用動態(tài)規(guī)劃的思想，以序列的每個點最為最右端，找出每個點作為最右端時的子序列長度的最大值，即問題的求解。因此，在計算前面的每個點的時候，將其結果保存下來，后面的點與前面的點的數(shù)值進行比較，如果大，則在其長度基礎上加1，并且找出所有可能情況下最長的保存為當前點的長度。形成遞歸。
具體實現(xiàn)代碼如下：
#include "stdio.h"
#include "stdlib.h"
#define MAXDATA 10000
int main(){
int data[MAXDATA]; /*數(shù)據(jù)序列*/
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]){ /*如果數(shù)據(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程序算法設計的學習有所幫助。
相關文章
本篇文章是對用C++實現(xiàn)雙向循環(huán)鏈表的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了如何利用C語言繪制一個正方體，文中的示例代碼講解詳細，具有一定的學習和借鑒價值，感興趣的小伙伴可以學習一下2023-01-01
這篇文章主要介紹了C++之構造函數(shù)默認值設置方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
大家都知道作為C++獲取輸入流的方法，幾乎在任何一本資料書上getline()方法和get()方法都作為入門級的方法進行講述，即便如此，筆者在學習C++的過程中仍經(jīng)常忘記這二者的使用要點，可能也有C++的初學者對這兩個方法還心存疑慮，本篇文章就這兩個方法的使用進行簡要闡述。2016-10-10
這篇文章主要為大家詳細介紹了C語言實現(xiàn)順序表的順序查找和折半查找，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
C語言中開辟內存有很多種方式，目前我們最常用的也就是數(shù)組，但數(shù)組是在我們用到他之前就得設定好它的長度，有時很不方便。隨意我們來探究動態(tài)內存管理2021-11-11
大家好，本篇文章主要講的是C語言數(shù)組詳細介紹，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)貪吃蛇小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
通過不同的方法，實現(xiàn)對所輸入字符串的反轉，具有一定的參考價值，需要的朋友們下面隨著小編來一起學習學習吧2021-06-06
這篇文章主要介紹了bilateral filter雙邊濾波器的通俗理解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03