題目描述
給定一個(gè)無序的整數(shù)數(shù)組,找到其中最長(zhǎng)上升子序列的長(zhǎng)度早敬。
示例
示例 1:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]天梧,它的長(zhǎng)度是 4。
說明
- 可能會(huì)有多種最長(zhǎng)上升子序列的組合,你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。
- 你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 鞍匾。
解答方法
方法一:動(dòng)態(tài)規(guī)劃
思路
狀態(tài)定義:
dp[i]的值代表 nums 前 i個(gè)數(shù)字的最長(zhǎng)子序列長(zhǎng)度。
轉(zhuǎn)移方程: 設(shè) j∈[0,i)骑科,考慮每輪計(jì)算新 dp[i]時(shí)橡淑,遍歷 [0,i)列表區(qū)間,做以下判斷:
- 當(dāng) nums[i] > nums[j]時(shí):nums[i] 可以接在 nums[j] 之后(此題要求嚴(yán)格遞增)纵散,此情況下最長(zhǎng)上升子序列長(zhǎng)度為 dp[j] + 1梳码;
- 此情況 下計(jì)算出的dp[j]+1 的最大值,為直到 i 的最長(zhǎng)上升子序列長(zhǎng)度(即dp[i] )伍掀。實(shí)現(xiàn)方式為遍歷 j時(shí)掰茶,每輪執(zhí)行 dp[i] = max(dp[i], dp[j] + 1)。轉(zhuǎn)移方程: dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)蜜笤。
- 當(dāng) nums[i] <= nums[j]時(shí): nums[i]nums[i] 無法接在 nums[j]之后濒蒋,此情況上升子序列不成立,跳過把兔。
轉(zhuǎn)移方程: dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)沪伙。
初始狀態(tài):
dp[i]dp[i] 所有元素置 11,含義是每個(gè)元素都至少可以單獨(dú)成為子序列县好,此時(shí)長(zhǎng)度都為 11围橡。
返回值:
返回 dpdp 列表最大值,即可得到全局最長(zhǎng)上升子序列長(zhǎng)度缕贡。
代碼
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums)==0:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
時(shí)間復(fù)雜度
O(n^2),遍歷計(jì)算 dpdp 列表需 O(N)O(N)翁授,計(jì)算每個(gè) dp[i]dp[i] 需 O(N)O(N)。
空間復(fù)雜度
O(N),dp列表占用線性大小額外空間晾咪。