C語(yǔ)言算法分析：求最長(zhǎng)的遞增數(shù)列
求最長(zhǎng)的遞增數(shù)列（Longest Increasing sequence， LIS）是一個(gè)比較常見(jiàn)的問(wèn)題。
給定數(shù)列 10， 22， 9， 33， 21， 50， 41， 60， 80，那么 LIS 為 10， 22， 33， 50， 60， 80
分析思路： 假定 array［0， 。.n-1］為輸入數(shù)據(jù)， LIS［i］為array［0， 。。.i-1］時(shí)的LIS （i 》0， i《= n），并且 array［i］是 LIS［i］的最后一個(gè)元素。
那么，LIS（i） = {1 + max（LIS（j））}， 其中， j 《 i， array［j］ 《= array［i］。
如果沒(méi)有滿(mǎn)足條件的j，LIS（i） = 1
方法1： 使用遞歸函數(shù)。
顯然，這是一個(gè)時(shí)間復(fù)雜度高的方法，很多函數(shù)重復(fù)調(diào)用了。
方法2：把中間結(jié)果保下來(lái)，避免重復(fù)計(jì)算：
聲明：本文內(nèi)容及配圖由入駐作者撰寫(xiě)或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。
舉報(bào)投訴
-
算法
+關(guān)注
關(guān)注
23文章
4629瀏覽量
93193 -
C語(yǔ)言
+關(guān)注
關(guān)注
180文章
7614瀏覽量
137433 -
遞增
+關(guān)注
關(guān)注
0文章
3瀏覽量
6702
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
10個(gè)經(jīng)典的C語(yǔ)言面試基礎(chǔ)算法及代碼
算法是一個(gè)程序和軟件的靈魂，作為一名優(yōu)秀的程序員，只有對(duì)一些基礎(chǔ)的算法有著全面的掌握，才會(huì)在設(shè)計(jì)程序和編寫(xiě)代碼的過(guò)程中顯得得心應(yīng)手。本文包括了經(jīng)典的Fibonacci數(shù)列、簡(jiǎn)易計(jì)算器、回文檢查、質(zhì)數(shù)
發(fā)表于 11-20 15:18
關(guān)于10大C語(yǔ)言基礎(chǔ)算法
這10大C語(yǔ)言基礎(chǔ)算法，在面試中會(huì)經(jīng)常遇到！ 算法是一個(gè)程序和軟件的靈魂，作為一名優(yōu)秀的程序員，只有對(duì)一些基礎(chǔ)的算法有著全面的掌握，才會(huì)在
發(fā)表于 04-29 14:30
C語(yǔ)言教程之波那契數(shù)列
C語(yǔ)言教程之波那契數(shù)列，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-22 11:06
?0次下載
C語(yǔ)言教程之求100～200之間的素?cái)?shù)
C語(yǔ)言教程之求100～200之間的素?cái)?shù)，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-22 11:06
?0次下載
C語(yǔ)言教程之求等差數(shù)列
C語(yǔ)言教程之求等差數(shù)列，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-22 17:45
?0次下載
C語(yǔ)言教程之使用while語(yǔ)句求n！
C語(yǔ)言教程之使用while語(yǔ)句求n！，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-25 14:43
?14次下載
C語(yǔ)言教程之求總數(shù)問(wèn)題
C語(yǔ)言教程之求總數(shù)問(wèn)題，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-25 15:03
?0次下載
C語(yǔ)言教程之求各元素之和問(wèn)題
C語(yǔ)言教程之求各元素之和問(wèn)題，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-25 15:03
?0次下載
C語(yǔ)言教程之求任意數(shù)的n次冪問(wèn)題
C語(yǔ)言教程之求任意數(shù)的n次冪問(wèn)題，很好的C語(yǔ)言資料，快來(lái)學(xué)習(xí)吧。
發(fā)表于 04-25 15:49
?0次下載
C語(yǔ)言算法之比賽求平均分
學(xué)技術(shù)，重在日拱一卒、一點(diǎn)一滴的積累。 今天一起分析C語(yǔ)言的算法之15：裁判求平均分。
發(fā)表于 04-24 09:26
?2040次閱讀
工商網(wǎng)監(jiān)
評(píng)論