PROBLEM LINK:Author: Ankush Khanna DIFFICULTY:Easy PREREQUISITES:Dynamic Programming, Binary Search, Longest Increasing SubSequence PROBLEM:Given an array $A$ of size $N$ containing integers, find the longest increasing subsequence (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. SubTask 1 Suppose $length[k]$ denotes the length of the LIS that ends at position $k$. $\therefore \space length[N  1]$ (0based indexing) 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 subtask 1, awarding us with 30 points. Just basic Dynamic Programming! SubTask 2 For this subtask, 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:Feel free to share your approach. If you have any queries, they are always welcome.
This question is marked "community wiki".
asked 06 Feb, 03:12
