[C++] 5 Solutions

• ``````class Solution {
public:
int lengthOfLIS(vector<int> &nums) {
return method5(nums); // or other methods
}
private:
//-------------------------------------------------------
// Brute-force, recursive => O(2^n)-time
int method1(vector<int> &nums) { // TLE
return helper1(nums);
}
int helper1(vector<int> nums) {
int n = nums.size();
if (n <= 0) return n;
int x = nums[n-1];
nums.pop_back();
vector<int> remain;
for (int i = 0; i < n-1; i++)
if (nums[i] < x) remain.push_back(nums[i]);
return max(1 + helper1(remain), helper1(nums));
}
//-------------------------------------------------------
// Brute-force, recursive => (Better than Method1) O(2^n)-time
int method2(vector<int> &nums) { // TLE
return helper2(nums, INT_MIN, 0);
}
int helper2(vector<int> &nums, int lo, int pos) {
if (pos >= nums.size()) return 0;
int x = 0; // length in which nums[pos] is chosen
if (nums[pos] > lo)
x = 1 + helper2(nums, nums[pos], pos + 1);
int y = helper2(nums, lo, pos + 1); // length in which nums[pos] is NOT chosen
return max(x, y);
}
//-------------------------------------------------------
// Dynamic Programming (top-down, recursive (method2) + memoization)
// O(n^2) time and space
int method3(vector<int> &nums) { // MLE
int n = nums.size();
nums.push_back(INT_MIN);
vector<vector<int>> memo (n + 1, vector<int>(n, -1));
return helper3(nums, n, 0, memo);
}
int helper3(vector<int> &nums, int loIndex, int pos, vector<vector<int>> &memo) {
if (pos >= nums.size() - 1) return 0;
if (memo[loIndex][pos] != -1) return memo[loIndex][pos];
int x = 0;
if (nums[pos] > nums[loIndex])
x = 1 + helper3(nums, pos, pos + 1, memo);
int y = helper3(nums, loIndex, pos + 1, memo);
return memo[loIndex][pos] = max(x, y);
}
//-------------------------------------------------------
// Dynamic Programming (Iterative)
int method4(vector<int> &nums) { // O(n^2) time and O(n)-space
int n = nums.size();
vector<int> dp (n, 1);
// dp[i] = length of longest increasing subsequence possible considering the array elements upto the i-th
//         index only, by necessarily including the i-th element.
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[i] > nums[j])
dp[i] = max(dp[i], 1 + dp[j]);
result = max(result, dp[i]);
}
return result;
}

//-------------------------------------------------------
// Dynamic Programming (Iterative) --> BEST ONE!
int method5(vector<int> &nums) { // O(nlgn) time and O(n)-space
int n = nums.size();
vector<int> dp (n); // dp[i] = last number (biggest number) in an LIS with length i + 1
int lastIndex = -1;
for (int num : nums) {
int i = BinarySearch(num, 0, lastIndex, dp); // search dp from 0 to lastIndex (inclusive)
dp[i] = num;
lastIndex = max(lastIndex, i);
}
return lastIndex + 1;
}
int BinarySearch(int val, int start, int end, vector<int> &dp) {
if (start > end) return start;
int mid = (start + end) / 2;
if (val == dp[mid]) return mid;
if (val < dp[mid]) return BinarySearch(val, start, mid - 1, dp);
return BinarySearch(val, mid + 1, end, dp);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.