原題
給定一個整數(shù)序列碉纺，找到最長上升子序列（LIS）钝荡，返回LIS的長度。
給出[5,4,1,2,3]滨溉，這個LIS是[1,2,3]什湘，返回 3
給出[4,2,4,5,3,7]，這個LIS是[4,4,5,7]晦攒，返回 4
最長上升子序列問題是在一個無序的給定序列中找到一個盡可能長的由低到高排列的子序列闽撤，這種子序列不一定是連續(xù)的或者唯一的。
解題思路
- 序列型動態(tài)規(guī)劃 - Sequence DP
- 判定條件：序列非集合脯颜，求最長
-
cache[i]表示以i結(jié)尾的最長子序列的長度 - 每次遍歷
0 ~ i-1如果存在nums[x] < nums[i]并且cache[x] + 1 > cache[i]則更新 - for循環(huán)中維護一個
res哟旗，即最大值
完整代碼
class Solution:
"""
@param nums: The integer array
@return: The length of LIS (longest increasing subsequence)
"""
def longestIncreasingSubsequence(self, nums):
cache = [1 for i in range(len(nums))]
res = 0
for i in range(1, len(nums)):
for j in range(i):
if nums[j] <= nums[i]:
if cache[j] + 1 > cache[i]:
cache[i] = cache[j] + 1
if cache[i] > res:
res = cache[i]
return res
