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ī)劃的思想，以序列的每個點(diǎn)最為最右端，找出每個點(diǎn)作為最右端時的子序列長度的最大值，即問題的求解。因此，在計算前面的每個點(diǎn)的時候，將其結(jié)果保存下來，后面的點(diǎn)與前面的點(diǎn)的數(shù)值進(jìn)行比較，如果大，則在其長度基礎(chǔ)上加1，并且找出所有可能情況下最長的保存為當(dāng)前點(diǎn)的長度。形成遞歸。
具體實現(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; /*給每一個序列點(diǎn)作為右端時的最大序列長度為1*/
}
for(int i=1;i<n;i++){
temp=1;
for(int j=0;j<i;j++){ /*與其前面的每一個進(jìn)行比較*/
if(data[i]>data[j]){ /*如果數(shù)據(jù)比前面的某一個的值大*/
if(lgs[i]+lgs[j]>temp){ /*找出該點(diǎn)的最大子序列長度*/
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程序算法設(shè)計的學(xué)習(xí)有所幫助。
相關(guān)文章
正如boost文檔所宣稱的，boost為shared_ptr提供了與內(nèi)置類型同級別的線程安全性。這包括：1. 同一個shared_ptr對象可以被多線程同時讀取。2. 不同的shared_ptr對象可以被多線程同時修改成2013-09-09
const引用是指向const對象的引用,可以讀取ref，但不能修改所以也就有將const變量賦值給非const引用是非法的,感興趣的朋友可以了解下，或許本文對你有所幫助2013-01-01
這篇文章主要介紹了C語言動態(tài)內(nèi)存分配的詳解的相關(guān)資料,這里提供了實現(xiàn)方法整理和出現(xiàn)錯誤的解決辦法，需要的朋友可以參考下2017-07-07
這篇文章主要介紹了在C++中加載TorchScript模型的方法，本文通過實例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02
本文詳細(xì)介紹了C語言中數(shù)據(jù)的存儲，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-05-05
詳解C++數(shù)組和數(shù)組名問題(指針、解引用)
這篇文章主要介紹了詳解C++數(shù)組和數(shù)組名問題(指針、解引用),指針的實質(zhì)就是個變量，它跟普通變量沒有任何本質(zhì)區(qū)別，指針本身是一個對象，同時指針無需在定義的時候賦值，具體內(nèi)容詳情跟隨小編一起看看吧2021-09-09
這篇文章主要給大家介紹了關(guān)于c語言階乘之和問題的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用c語言具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
初始化列表是類中構(gòu)造函數(shù)的一部分,用于實例化類中變量時賦初值,下面這篇文章主要給大家介紹了關(guān)于C++學(xué)習(xí)筆記之初始化列表的相關(guān)資料,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了C語言正確使用extern關(guān)鍵字，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
詳解C語言中printf輸出的相關(guān)函數(shù)
這篇文章主要介紹了C語言中printf輸出的相關(guān)函數(shù)總結(jié),是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-08-08