給定一個(gè)長度為 n 的數(shù)組 arr，求它的最長嚴(yán)格上升子序列的長度。 所謂子序列，指一個(gè)數(shù)組刪掉一些數(shù)（也可以不刪）之后，形成的新數(shù)組。例如 [1,5,3,7,3] 數(shù)組，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 則不是它的子序列。 我們定義一個(gè)序列是 嚴(yán)格上升 的，當(dāng)且僅當(dāng)該序列不存在兩個(gè)下標(biāo) 和 滿足 且 。 數(shù)據(jù)范圍： , 要求：時(shí)間復(fù)雜度 ， 空間復(fù)雜度
輸入描述:
第一行輸入一個(gè)正整數(shù) n ，表示數(shù)組的長度 第二行輸入 n 個(gè)整數(shù)表示數(shù)組的每個(gè)元素。
輸出描述:
輸出最長嚴(yán)格上升子序列的長度
示例1
說明
該數(shù)組最長上升子序列為 [1,2,3,7] ，長度為4
加載中...