300. Longest Increasing Subsequence

Description:

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

Algorithm:

About explanation of Code1, 3, please refer to:

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)