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