給定一個(gè)長(zhǎng)度為 n 的數(shù)組a,求它的最長(zhǎng)嚴(yán)格上升子序列的長(zhǎng)度。 所謂子序列,指一個(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ù)雜度
示例1
說(shuō)明
最長(zhǎng)上升子序列為 [1,4,5,6] ,長(zhǎng)度為4。
加載中...