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ù)。
顯然，這是一個時間復雜度高的方法，很多函數(shù)重復調(diào)用了。
方法2：把中間結(jié)果保下來，避免重復計算：
聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學習之用，如有內(nèi)容侵權或者其他違規(guī)問題，請聯(lián)系本站處理。
舉報投訴
-
算法
+關注
關注
23文章
4775瀏覽量
97618 -
C語言
+關注
關注
183文章
7642瀏覽量
145118 -
遞增
+關注
關注
0文章
3瀏覽量
6785
發(fā)布評論請先 登錄
相關推薦
熱點推薦
10個經(jīng)典的C語言面試基礎算法及代碼
算法是一個程序和軟件的靈魂，作為一名優(yōu)秀的程序員，只有對一些基礎的算法有著全面的掌握，才會在設計程序和編寫代碼的過程中顯得得心應手。本文包括了經(jīng)典的Fibonacci數(shù)列、簡易計算器、回文檢查、質(zhì)數(shù)
發(fā)表于 11-20 15:18
關于10大C語言基礎算法
這10大C語言基礎算法，在面試中會經(jīng)常遇到！ 算法是一個程序和軟件的靈魂，作為一名優(yōu)秀的程序員，只有對一些基礎的算法有著全面的掌握，才會在
發(fā)表于 04-29 14:30
工商網(wǎng)監(jiān)
評論