Longest Increasing Subsequence

LIS is a famous algorithm problem that can be solved by dynamic programming. It is to find the longest subsequence of a given sequence where the subsequence’s elements are sorted from lowest to highest. For example, given the sequence A = 1 6 2 5 7 3 5 6, the longest increasing subsequence has length 5: it is 1 2 3 5 6.
Let’s think about finding the length of LIS of a given sequence. There are two algorithms of solving this with dynamic programming.

1. O(N^2) with dynamic programming

Let’s define an array D where D[i] is the length of the LIS ending at index i such that A[i] is the last element of the LIS. In order for A[i] to be the last value of a LIS, A[i] must be greater than the last value of current LIS.

Let’s look at this example.

i = 1

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1              

LIS is 1 and D[1] = 1.

i = 2

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2            

A[2] = 6 and 6 > 1, so LIS is 1 6 and D[2] = D[1] + 1 = 2.

i = 3

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2 2          

A[3] = 2. Because 2 < 6 and 2 > 1, LIS is 1 2 and D[2] = 2.

i = 4

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2 2 3        

A[4] = 5 and 5>1, 5>2, 5<6, so A[4] can be followed by A[1] or A[3]. Our goal is to find the longest increasing subsequence, so A[4] must be followed by A[3]. Hence LIS is 1 2 5.

i = 5

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2 2 3 4      

A[5] = 7 and 7 > 1, 7 > 6, 7 > 2, and 7 > 5. LIS is 1 2 5 7 and D[5] = 4.

i = 6

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2 2 3 4 3    

LIS is 1 2 3.

i = 7

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2 2 3 4 3 4  

LIS is 1 2 3 5.

i = 8

i 1 2 3 4 5 6 7 8
A 1 6 2 5 7 3 5 6
D 1 2 2 3 4 3 4 5

LIS is 1 2 3 5 6.

The answer is the largest value of the array D, which is 5.
This algorithm traverses through the input array (O(N)), and for each element i it finds a j though linear search(O(N)), as a result running in O(N^2) complexity.

This is my source code.

#include <iostream>
#define MAX 1001
using namespace std;

int N;
int A[MAX]; // input array
int D[MAX]; // ans[i]: the length of the LIS ending at index i such at box[i] is the last element of the LIS

void solve() {
    ans[1] = 1;
    for (int i = 1; i <= N; i++) D[i] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (A[j] < A[i]) {
            /*
            Determines if we can increase the length. 
            It took a while for me to understand why I needed this conditional statement below.
            Because the array D was initialised to 1, I thought this statement is always true regardless of the values of i and j.
            Later I realised that as j increases, i increases in some case.
            So without this code, the problem of D[i] being updated to a smaller value occurs.
            */
            if (D[i] < D[j] + 1) D[i] = D[j] + 1;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); // for faster i/o
    cin.tie(0);
    
    // input
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    
    solve();
    
    // our answer is the largest value the array D.
    int max = D[1];
    for (int i = 2; i <= N; i++) {
        if (max < D[i]) max = D[i];
    }
    cout << max << endl;
    return 0;
}

References