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