×

# LAEDDIS - Editorial

Author: Ankush Khanna

Easy

# 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.

Suppose $length[k]$ denotes the length of the LIS that ends at position $k$. $\therefore \space length[N - 1]$ (0-based 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 sub-task 1, awarding us with 30 points. Just basic Dynamic Programming!

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

Feel free to share your approach. If you have any queries, they are always welcome.

This question is marked "community wiki".

53
accept rate: 33%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,678
×3,763
×2,169
×1,038
×790
×52
×14
×14