国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

300. Longest Increasing Subsequence -Medium

2019-11-11 07:10:23
字體:
來源:轉載
供稿:網友

Question

Given an unsorted array of integers, find the length of longest increasing subsequence.

Your algorithm should run in O(n2) complexity.

給出一個未排序的整數數組,找出最長增長子序列的長度(算法時間復雜度應該是O(N ^ 2))

Example

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.

Solution

動態規劃解。定義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
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 寻乌县| 射洪县| 拉孜县| 瑞丽市| 巨鹿县| 巴中市| 大姚县| 娄底市| 苍山县| 健康| 朝阳区| 乐昌市| 合水县| 丰城市| 安平县| 石楼县| 双鸭山市| 河池市| 犍为县| 延长县| 扶余县| 顺义区| 成都市| 黑河市| 蛟河市| 河南省| 望都县| 兴安县| 汝阳县| 阳高县| 定南县| 钟山县| 安化县| 西盟| 建宁县| 泸州市| 西峡县| 如东县| 天祝| 石首市| 奉新县|