The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Complexity

The longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.

Dynamic programming approach has complexity O(n * n).

Example

In the first 16 terms of the binary Van der Corput sequence

1

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

1

0, 2, 6, 9, 11, 15.

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

1
2
3

0, 4, 6, 9, 11, 15 or
0, 2, 6, 9, 13, 15 or
0, 4, 6, 9, 13, 15

are other increasing subsequences of equal length in the same input sequence.

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

    // Initialize LIS values for all indexes
for (let i = 0; i < A.length; i++) {
  LIS[i] = 1;
}

console.log('Calculating Longest Increasing Subsequence values in bottom up manner ');

// Compute optimized LIS values in bottom up manner
for (let i = 1; i < A.length; i++) {
  
  for (let j = 0; j < i; j++) {
    
    if (A[i] > A[j] && LIS[i] < LIS[j] + 1) {
      LIS[i] = LIS[j] + 1;
      
      console.log(` LIS[${i}] = ${LIS[i]}`);
      
    }
  }
  
}

// Pick maximum of all LIS values

console.log('Now calculate maximum of all LIS values ');

let max = LIS[0];
for (let i = 1; i < A.length; i++) {
  if (max < LIS[i]) {
    max = LIS[i];
  }
}

console.log(`Longest Increasing Subsequence = max of all LIS = ${max}`);