C語言算法分析：求最長的遞增數(shù)列
求最長的遞增數(shù)列（Longest Increasing sequence， LIS）是一個比較常見的問題。
給定數(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］時的LIS （i 》0， i《= n），并且 array［i］是 LIS［i］的最后一個元素。
那么，LIS（i） = {1 + max（LIS（j））}， 其中， j 《 i， array［j］ 《= array［i］。
如果沒有滿足條件的j，LIS（i） = 1
方法1： 使用遞歸函數(shù)。
顯然，這是一個時間復(fù)雜度高的方法，很多函數(shù)重復(fù)調(diào)用了。
方法2：把中間結(jié)果保下來，避免重復(fù)計算：
聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。
舉報投訴
-
算法
+關(guān)注
關(guān)注
23文章
4784瀏覽量
98042 -
C語言
+關(guān)注
關(guān)注
183文章
7644瀏覽量
145575 -
遞增
+關(guān)注
關(guān)注
0文章
3瀏覽量
6793
發(fā)布評論請先 登錄
相關(guān)推薦
熱點推薦
10個經(jīng)典的C語言面試基礎(chǔ)算法及代碼
算法是一個程序和軟件的靈魂，作為一名優(yōu)秀的程序員，只有對一些基礎(chǔ)的算法有著全面的掌握，才會在設(shè)計程序和編寫代碼的過程中顯得得心應(yīng)手。本文包括了經(jīng)典的Fibonacci數(shù)列、簡易計算器、回文檢查、質(zhì)數(shù)
發(fā)表于 11-20 15:18
關(guān)于10大C語言基礎(chǔ)算法
這10大C語言基礎(chǔ)算法，在面試中會經(jīng)常遇到！ 算法是一個程序和軟件的靈魂，作為一名優(yōu)秀的程序員，只有對一些基礎(chǔ)的算法有著全面的掌握，才會在
發(fā)表于 04-29 14:30
C語言教程之求100～200之間的素數(shù)
C語言教程之求100～200之間的素數(shù)，很好的C語言資料，快來學(xué)習(xí)吧。
發(fā)表于 04-22 11:06
?0次下載
工商網(wǎng)監(jiān)
評論