class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def helper(pre, cur):
if cur == len(nums):
return 0
taken = 0
if nums[cur] > pre:
taken = 1+helper(nums[cur], cur+1)
untaken = helper(pre, cur+1)
return max(taken, untaken)
return helper(float('-inf'), 0)
超时
动态规划
dp数组存当前数字最长上升子序列。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
size = len(nums)
if size <= 1:
return size
dp = [1]*size
res = 1
for i in range(1, size):
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
res = max(res, dp[i])
return res
Runtime: 1172 ms, faster than 23.13% of Python3 online submissions for Longest Increasing Subsequence.
Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Longest Increasing Subsequence.
var lengthOfLIS = function(nums) {
const len = nums.length
if (len <= 1) {
return len
}
let dp = new Array(len);
for (let i = 0; i < len; i++) {
dp[i] = 1
}
let ans = 1
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
ans = Math.max(ans, dp[i])
}
return ans
};
Runtime: 72 ms, faster than 59.59% of JavaScript online submissions for Longest Increasing Subsequence.
Memory Usage: 34.8 MB, less than 55.56% of JavaScript online submissions for Longest Increasing Subsequence.
二分查找
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
top = [0]*len(nums)
piles = 0
for i in range(0, len(nums)):
left = 0
right = piles
while left < right:
mid = (left+right) >> 1
if top[mid] < nums[i]:
left = mid+1
else:
right = mid
if left == piles:
piles += 1
top[left] = nums[i]
return piles
Runtime: 32 ms, faster than 99.55% of Python3 online submissions for Longest Increasing Subsequence.
Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Longest Increasing Subsequence.