Given an unsorted array of integers, find the length of longest increasing subsequence.
Your algorithm should run in O(n2) complexity.
給出一個未排序的整數數組，找出最長增長子序列的長度（算法時間復雜度應該是O(N ^ 2)）
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
動態規劃解。定義dp[i]：以第i個元素結尾的最長子序列長度（不是整個序列的最長子序列），遞推關系式：dp[i] = max{dp[j] > dp[i]} + 1 (0 <= j < i )，并且維護一個最大子序列長度，每當dp[i]更新時同時更新最長子序列長度。
class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 0: return 0 dp = [1] * len(nums) max_len = 1 # 維護一個最大子序列長度 for index_n, n in enumerate(nums): for i in range(index_n): if n > nums[i] and dp[i] + 1 > dp[index_n]: dp[index_n] = dp[i] + 1 max_len = max(max_len, dp[index_n]) return max_len新聞熱點
疑難解答
