🐟 Blog

Longest Increasing Subsequence

February 11, 2021


Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Key Intuition

To build the recurrence relation, we could ask ourselves whether the answer for nβˆ’1n - 1 elements help us solve the entire sequence.

Suppose we know the longest increasing sequence in (S0,S1,...,Snβˆ’1)(S_0, S_1, ..., S_{n-1}) is of length 55, and that Sn=8S_n = 8. Will the longest increasing subsequence of SS be 55 or 66? It depends on whether the length-55 sequence ends with a value less than 88.

Therefore, we really need to check every number (S0,S1,...Sj)(S_0, S_1,...S_j) where j<nj < n and see whether Sn>SjS_n > S_j.


public int lengthOfLIS(int[] nums) {
  int result = 1;
  int dp[] = new int[nums.length];
  Arrays.fill(dp, 1);

  for (int i = 1; i < nums.length; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
    result = Math.max(dp[i], result);

  return result;

Best Explanation

Β© Attribution Required | θ½¬θ½½θ―·ζ³¨ζ˜ŽεŽŸδ½œθ€…δΈŽζœ¬η«™ι“ΎζŽ₯
Β© 2022 yujinyan.me