SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Intermediate

Longest Increasing Subsequence Visualizer

dp[i] is the length of the longest increasing run that ends exactly at a[i]. Look back at every j < i with a smaller value and extend the best one.

Start the Longest Increasing Subsequence simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n²)
Average timeO(n²)
Worst timeO(n²)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. dp[i] will hold the longest increasing subsequence that ends at a[i].
  2. Every value alone is a run of length 1, so dp[0] starts at 1.
  3. dp[0] = 1. Best so far: 1.
  4. Every value alone is a run of length 1, so dp[1] starts at 1.
  5. 10 ≥ 9, so 9 can’t extend a run ending at 10.
  6. dp[1] = 1. Best so far: 1.
  7. Every value alone is a run of length 1, so dp[2] starts at 1.
  8. 10 ≥ 2, so 2 can’t extend a run ending at 10.
  9. 9 ≥ 2, so 2 can’t extend a run ending at 9.
  10. dp[2] = 1. Best so far: 1.
  11. Every value alone is a run of length 1, so dp[3] starts at 1.
  12. 10 ≥ 5, so 5 can’t extend a run ending at 10.
  13. 9 ≥ 5, so 5 can’t extend a run ending at 9.
  14. 2 < 5, so extend the run ending at 2: dp[3] = 1 + 1 = 2.
  15. dp[3] = 2. Best so far: 2.
  16. Every value alone is a run of length 1, so dp[4] starts at 1.
  17. 10 ≥ 3, so 3 can’t extend a run ending at 10.
  18. 9 ≥ 3, so 3 can’t extend a run ending at 9.
  19. 2 < 3, so extend the run ending at 2: dp[4] = 1 + 1 = 2.
  20. 5 ≥ 3, so 3 can’t extend a run ending at 5.
  21. … 22 more steps …
  22. 7 < 18, so extend the run ending at 7: dp[7] = 3 + 1 = 4.
  23. 101 ≥ 18, so 18 can’t extend a run ending at 101.
  24. dp[7] = 4. Best so far: 4.
  25. The longest increasing subsequence has length 4, for example 2, 5, 7, 101.

Try it with your own input →

1D DP: longest increasing subsequence in Java, Python, C++, C and JavaScript

int lengthOfLIS(int[] a) {
  int[] dp = new int[a.length];
  int best = 0;
  for (int i = 0; i < a.length; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i])
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return best;
}
def length_of_lis(a):
    dp = [0] * len(a)
    best = 0
    for i in range(len(a)):
        dp[i] = 1
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        best = max(best, dp[i])
    return best
int lengthOfLIS(const vector<int>& a) {
  vector<int> dp(a.size());
  int best = 0;
  for (int i = 0; i < (int)a.size(); i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i])
        dp[i] = max(dp[i], dp[j] + 1);
    }
    best = max(best, dp[i]);
  }
  return best;
}
int lengthOfLIS(int a[], int n) {
  int dp[n];
  int best = 0;
  for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i] && dp[j] + 1 > dp[i])
        dp[i] = dp[j] + 1;
    }
    if (dp[i] > best) best = dp[i];
  }
  return best;
}
function lengthOfLIS(a) {
  const dp = new Array(a.length);
  let best = 0;
  for (let i = 0; i < a.length; i++) {
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
      if (a[j] < a[i])
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return best;
}

In an interview

LeetCode 300, Longest Increasing Subsequence. Same shape: 354 Russian Doll Envelopes, 1048 Longest String Chain.

The follow-up is O(n log n): keep a list of the smallest possible tail for each length and binary-search where each value goes.

More dynamic programming