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