How to Find the Length of the Longest Increasing Subsequence usi
- 时间:2020-09-18 17:01:02
- 分类:网络文摘
- 阅读:90 次
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.
Follow up: Could you improve it to O(nlogn) time complexity?
Length of the Longest Increasing Subsequence using DP Algorithm
Surely, we can bruteforce, but that will take O(2^n) complexity i.e. each number has two choices: take or not take. This is not ideal. We could use f[i] to represent the longest length subsequence that ending at element nums[i]. Thus, we can reduce the runtime complexity to O(N^2) by checking each pair of (nums[j], nums[i]) and update f[i] = max(f[i], f[j] + 1) if nums[j] is smaller than nums[i].
The Longest Increasing Subsequence (LIS) can be computed via the following Dynamic Programming Algorithm i.e. C++.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.empty()) return 0; vector<int> f(nums.size(), 1); int ans = 1; for (int i = 1; i < nums.size(); ++ i) { for (int j = 0; j < i; ++ j) { if (nums[j] < nums[i]) { f[i] = max(f[i], f[j] + 1); ans = max(ans, f[i]); } } } return ans; } }; |
class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.empty()) return 0; vector<int> f(nums.size(), 1); int ans = 1; for (int i = 1; i < nums.size(); ++ i) { for (int j = 0; j < i; ++ j) { if (nums[j] < nums[i]) { f[i] = max(f[i], f[j] + 1); ans = max(ans, f[i]); } } } return ans; } };
Then, we need to find out the maximum value in f[0] to f.back(). The space requirement is O(N).
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:不同包装的牛奶,你知道该如何选择吗 冬天吃羊肉如何去掉羊膻味及饮食禁忌 适度喝啤酒预防骨质疏松保持关节弹性 关于鸡蛋营养及其食用方法的十大误区 腊肉的风味和特点及腊肉的制作全过程 腊肉的营养价值及腊肉的食用禁忌 煲汤的诀窍及胡萝卜熟吃煮汤更营养 胡萝卜不但可以保护视力还对精子有益 节令食品年糕的营养价值与食用禁忌 如何吃辣椒不上火?怎样吃辣椒更健康?
- 评论列表
-
- 添加评论