PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming, Binary Search, Longest Increasing Sub-Sequence
PROBLEM:
Given an array A of size N containing integers, find the longest increasing sub-sequence (LIS) of A.
QUICK EXPLANATION:
Key to AC: Use binary search based dynamic programming algorithm (Patience Sort based) to find LIS of an array.
EXPLANATION:
This is rather a very direct implementation problem. Though it involves Dynamic Programming, but this is readily available to be solved. It was just the language of the problem and problem statement framing that kept it somewhat hidden.
There are two versions of finding the size of LIS in a sequence. The first one is plain dynamic programming solution that works in O(N^2) time with O(N) auxiliary space. And the second one works in O(N \log_2 N) time with O(N) auxiliary space.
Sub-Task 1
Suppose length[k] denotes the length of the LIS that ends at position k in 0-based indexing.
\therefore \space \max{\{ length[0 \dots N - 1] \}} will give us the length of the LIS in the given sequence.
for (int k = 0; k < N; k++) {
length[k] = 1;
for (int i = 0; i < k; i++) {
if (A[i] < A[k]) {
length[k] = max(length[k], length[i] + 1);
}
}
}
This C++ code runs in O(N^2) time, which would suffice our constraints for sub-task 1, awarding us with 30 points. Just basic Dynamic Programming!
Sub-Task 2
For this sub-task, we must go below O(N^2) time, and luckily we have binary search based dynamic programming algorithm for LIS which uses patience sort like structure (here) which works in O(N \log_2 N) time due to binary search. Detailed explanation about LIS algorithms can be found in the links provided in this editorial.
COMPLEXITY:
O(N \log_2 N) time and O(N) auxiliary space.
SOLUTION:
Setter’s Solution [Plain Text]
Feel free to share your approach. If you have any queries, they are always welcome.