# 300. Longest Increasing Subsequence

Description:

https://leetcode.com/problems/longest-increasing-subsequence/#/description

Algorithm:

https://leetcode.com/articles/longest-increasing-subsequence/

For Code2:

There are two steps:

• Step1:
• Use array to record the index of number which is larger than num[i], priority: position
• Use another array to record the index of number which is larger than num[i], priority: value
• Step2
• from end to start, find the max length of array
• length = `max(lengths[posLarger[i]], lengths[valLarger[i]]) + 1;`

Code1:

```class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.size() == 0) { return 0; } vector<int> dp = vector<int>(nums.size(), 0); dp[0] = 1; int maxans = 1; for (int i = 1; i < nums.size(); i++) { int maxval = 0; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { maxval = max(maxval, dp[j]); } } dp[i] = maxval + 1; maxans = max(maxans, dp[i]); } return maxans; } };```

Code2:

```class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> lengths = vector<int>(n, 1); vector<int> posLarger = vector<int>(n, INT_MIN); vector<int> valLarger = vector<int>(n, -1); posLarger[n-1] = -1; for (int i = 0; i < nums.size() - 1;i++) { for (int j = i + 1; j < nums.size();j++) { if (nums[j] > nums[i]) { if (posLarger[i] == INT_MIN) posLarger[i] = j; if (valLarger[i] == -1) valLarger[i] = j; else if (nums[j] < nums[valLarger[i]]) valLarger[i] = j; } } if (posLarger[i] == INT_MIN) { posLarger[i] = -1; valLarger[i] = -1; } } for (int i = nums.size() - 1; i >= 0;i--) { if (posLarger[i] >= 0) lengths[i] = max(lengths[posLarger[i]], lengths[valLarger[i]]) + 1; } int result = 1; for (int i = 0;i < nums.size();i++) { if (lengths[i] > result) result = lengths[i]; } return result; } };```

Code3:

```class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> res; for (int i = 0; i<nums.size(); i++) { auto it = std::lower_bound(res.begin(), res.end(), nums[i]); if (it == res.end()) res.push_back(nums[i]); else *it = nums[i]; } return res.size(); } };```

Time & Space:

Code1:

// Simple DP solution, beats 10.42%
// Time: O(n2), Space: O(n)

Code2:

// My solution, beats 49.5%
// Time: O(n2), Space: O(n)

Code3:

Time: O(nlogn), Space: O(n)