C語言算法分析：求最長的遞增數列
求最長的遞增數列（Longest Increasing sequence， LIS）是一個比較常見的問題。
給定數列 10， 22， 9， 33， 21， 50， 41， 60， 80，那么 LIS 為 10， 22， 33， 50， 60， 80
分析思路： 假定 array［0， 。.n-1］為輸入數據， 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： 使用遞歸函數。
顯然，這是一個時間復雜度高的方法，很多函數重復調用了。
方法2：把中間結果保下來，避免重復計算：
聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容侵權或者其他違規問題，請聯系本站處理。
舉報投訴
-
算法
+關注
關注
23文章
4682瀏覽量
94330 -
C語言
+關注
關注
180文章
7626瀏覽量
139622 -
遞增
+關注
關注
0文章
3瀏覽量
6718
發布評論請先 登錄
相關推薦
10個經典的C語言面試基礎算法及代碼
算法是一個程序和軟件的靈魂，作為一名優秀的程序員，只有對一些基礎的算法有著全面的掌握，才會在設計程序和編寫代碼的過程中顯得得心應手。本文包括了經典的Fibonacci數列、簡易計算器、回文檢查、質數
發表于 11-20 15:18
工商網監
評論