Find length of the longest increasing subsequence (LIS) in the array using DP

Technology Community › Category: Dynamic Programming › Find length of the longest increasing subsequence (LIS) in the array using DP

0 Vote Up Vote Down

VietMX Staff asked 3 years ago

Problem

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.

Consider:

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

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

a longest increasing subsequence is

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,

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.

Let’s assume the indices of the array are from 0 to N – 1.
Let’s define DP[i] to be the length of the LIS (Longest increasing subsequence) which is ending at element with index i.

DP[0] = 1; // length of LIS for the first element is always 1
int maxLength = 1;

To compute DP[i] for each i > 0 we look at all indices j < i and check both:

if DP[j] + 1 > DP[i] and
array[j] < array[i] (we want it to be increasing).

If this is true we can update the current optimum for DP[i].

for (int i = 1; i < N; i++)
   {
      DP[i] = 1;
      prev[i] = -1;

      for (int j = i - 1; j >= 0; j--)
         if (DP[j] + 1 > DP[i] && array[j] < array[i])
         {
            DP[i] = DP[j] + 1;
            prev[i] = j;
         }

      if (DP[i] > maxLength)
      {
         bestEnd = i;
         maxLength = DP[i];
      }
   }

To find the global optimum for the array you can take the maximum value from DP [0...N - 1]
Use the array prev to be able later to find the actual sequence not only its length. Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.

Complexity Analysis

Time complexity : O(n^2). Two loops of n are there.
Space complexity : O(n). DP array of size n is used.

Implementation

/**
 * Dynamic programming approach to find longest increasing subsequence.
 * Complexity: O(n * n)
 *
 * @param {number[]} sequence
 * @return {number}
 */
export default function dpLongestIncreasingSubsequence(sequence) {
  // Create array with longest increasing substrings length and
  // fill it with 1-s that would mean that each element of the sequence
  // is itself a minimum increasing subsequence.
  const lengthsArray = Array(sequence.length).fill(1);

  let previousElementIndex = 0;
  let currentElementIndex = 1;

  while (currentElementIndex < sequence.length) {
    if (sequence[previousElementIndex] < sequence[currentElementIndex]) {
      // If current element is bigger then the previous one then
      // current element is a part of increasing subsequence which
      // length is by one bigger then the length of increasing subsequence
      // for previous element.
      const newLength = lengthsArray[previousElementIndex] + 1;
      if (newLength > lengthsArray[currentElementIndex]) {
        // Increase only if previous element would give us bigger subsequence length
        // then we already have for current element.
        lengthsArray[currentElementIndex] = newLength;
      }
    }

    // Move previous element index right.
    previousElementIndex += 1;

    // If previous element index equals to current element index then
    // shift current element right and reset previous element index to zero.
    if (previousElementIndex === currentElementIndex) {
      currentElementIndex += 1;
      previousElementIndex = 0;
    }
  }

  // Find the biggest element in lengthsArray.
  // This number is the biggest length of increasing subsequence.
  let longestIncreasingLength = 0;

  for (let i = 0; i < lengthsArray.length; i += 1) {
    if (lengthsArray[i] > longestIncreasingLength) {
      longestIncreasingLength = lengthsArray[i];
    }
  }

  return longestIncreasingLength;
}

Question Tags: Dynamic Programming, Middle Level