Logicmojo - Updated Aug 28, 2021
Problem Statement: Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence : Given an array A, find the length of the longest strictly increasing subsequence (LIS). A subsequence is a sequence that can be derived from an array by deleting some or no elements such that the order of the remaining elements remain the same.
Examples: A: [10, 20, 2, 5, 3, 8, 8, 25, 6]
Result: 4
Explanation: Longest increasing subsequence: [2, 5, 8, 25]
Approach 1: Dynamic Programming
The basic principle of Longest increasing subsequence is that if your solution has a recursive structure, then you can:
1. Break down the problem into smaller repeating sub-problems.
2. Store the solutions of the sub-problems and use them later when needed
For example, LIS(arr, 0) and LIS(arr, 1) are re-calculated and required again and again. Alternatively, once computed, we can store them in an array, and use this result whenever it is needed.
Hence, now we have to account for an additional array. Let's call this array LISArr, which stores the value of LIS(arr, n) at index n.
1. Initialize each element of LISArr to zero.
2. If LIS(arr, n) is required, then check the value of LISArr[n].
3. If LISArr[n] is zero, then compute LIS(arr,n) and store in LISArr[n]
4. If LISArr[n] is greater than zero, then simply use its value from the array.
Now it is time to change the prior pseudo-code to incorporate dynamic programming. Only the LIS(arr, n) routine needs to be changed, with one additional parameter to include the array LISArr.
We can see that the time complexity of this pseudo-code is still quadratic, i.e., O(n2). The LISDP function runs for each item of the array and for each item, LIS runs at the most n times. This makes the overall complexity O(n2).
C++ Implementation:
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (nums[i] > nums[j] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; return *max_element(dp.begin(), dp.end()); } };
Python Implementation:
class Solution: def lengthOfLIS(self, nums): n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j] and dp[i] < dp[j] + 1: dp[i] = dp[j] + 1 return max(dp) ob1 = Solution() print(ob1.lengthOfLIS([10, 20, 2, 5, 3, 8, 8, 25, 6]))
Approach 2: Using Binary Search
LIS using dynamic programming still requires O(n^2) computations. Can you find an improved algorithm that uses O(n log n) time?
To understand how the solution of finding LIS can be made more efficient, let's review binary search first. We can improve upon the computation time by making use of the fact that it takes O(log n) time to search for an item in a sorted array when using binary search.
Coming back to finding LIS-- we'll use an intermediate array again called LISArray. Let us define its purpose in this instance, and highlight a few important points:
1. We will use LISArray to store indices of the input array arr.
2. We'll also use LISArray to keep track of the longest subsequence found so far.
3. LISArray[j]: LISArray[j] will map to the index of the smallest item of arr that's the last item for a subsequence of length j.
4. arr[LISArray[j]]: Ending element of subsequence of length j.
5. Size of LISArray[j] = (Size of arr)+ 1, as LISArr[j] has information on subsequence of length j, indices start at zero so we need an additional element to store the maximum possible length.
6. LISArray[0] is unused
7. Maximum index of LISArray can be at (Size of arr).
C++ Implementation:
class Solution { public: vector<int> pathOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> sub, subIndex; // Store index instead of value for tracing path purpose vector<int> path(n, -1); // path[i] point to the index of previous number in LIS for (int i = 0; i < n; ++i) { if (sub.empty() || sub[sub.size() - 1] < nums[i]) { path[i] = sub.empty() ? -1 : subIndex[sub.size() - 1]; sub.push_back(nums[i]); subIndex.push_back(i); } else { int idx = lower_bound(sub.begin(), sub.end(), nums[i]) - sub.begin(); path[i] = idx == 0 ? -1 : subIndex[idx - 1]; sub[idx] = nums[i]; subIndex[idx] = i; } } vector<int> ans; int t = subIndex[subIndex.size() - 1]; while (t != -1) { ans.push_back(nums[t]); t = path[t]; } reverse(ans.begin(), ans.end()); return ans; } }; int main() { vector<int> nums = {2, 6, 8, 3, 4, 5, 1}; vector<int> res = Solution().pathOfLIS(nums); // [2, 3, 4, 5] for (int x : res) cout << x << " "; return 0; }
Python Implementation:
def getLIS(nums): # Check if the sequence is empty if not nums: return nums M = [None] * len(nums) P = [None] * len(nums) # We know that there is at least an increasing subsequence of length one # which is the first element L = 1 M[0] = 0 # So we try to increase the length L from second item. for i in range(1, len(nums)): # We do a binary search just like the previous solution left = 0 right = L # Check the right bound if nums[M[right-1]] < nums[i]: j = right else: while right - left > 1: mid = (right + left) // 2 if nums[M[mid-1]] < nums[i]: left = mid else: right = mid j = left P[i] = M[j-1] if j == L or nums[i] < nums[M[j]]: M[j] = i L = max(L, j+1) # Now we need to get the sequence of length L # The result will be inversed seq = [] i = M[L-1] for _ in range(L): seq.append(nums[i]) i = P[i] return len(seq[::-1]) print(getLIS([10, 20, 2, 5, 3, 8, 8, 25, 6]))
Time Complexity: O(nlogn)
Space Complexity: O(n)
With this article at Logicmojo, you must have the complete idea of solving Longest Increasing Subsequence (LIS) problem.