給定一個無序的整數數組酪捡,找到其中最長上升子序列的長度。
輸入:[10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是[2,3,7,101]尸红,它的長度是4吱涉。
解:我們使用d[ i ]來表示前 i 個字符最長的長度刹泄,第 i 個字符如果大于最長上升子序列的最后一個字符時,那么最長上升子序列就可以增加一個怎爵,長度則可以加一特石。我們需要維護一個數組d[ i ],計算第 i 個數字時,則遍歷d[ i ]鳖链。如果nums[ i ] > nums[ j ] (i > j),則d[ i ] = d[ j ] + 1,否則d[ i ] = d[ j ]