The Longest Increasing Subsequence (LIS) pattern is a fundamental Dynamic Programming pattern for problems where we select elements from a sequence while preserving their relative order.

Unlike a subarray, a subsequence may skip elements.

The core idea is:

Define the best valid subsequence ending at each position, then extend it when the current element is compatible.

Focus on recognizing:

“Choose elements in order + skipping allowed + longest / maximum / count” = LIS-style DP

Pattern Table

Pattern	Typical Questions	Trigger	Main Technique
Classic LIS	Longest increasing subsequence	increasing + subsequence	O(n²) DP
LIS Binary Search	Large LIS constraints	need O(n log n)	Tails + binary search
Maximum Sum LIS	Maximum sum increasing subsequence	increasing + max sum	O(n²) DP
Number of LIS	Count longest subsequences	count LIS	Length + count DP
Longest Bitonic	Increase then decrease	mountain / bitonic	LIS + LDS
Russian Doll Envelopes	Maximum nesting	envelopes / nesting	Sort + LIS
Divisible Subset	Largest divisible subset	divisible	LIS-style DP
Pair Chain	Longest valid chain	chain / pairs	Sort + DP / Greedy
Box Stacking	Maximum stack height	dimensions / stack	Sort + LIS-style DP
Building Bridges	Maximum non-crossing bridges	bridges / crossing	Sort + LIS

Mental Trigger

Preserve order → Skip elements → Define compatibility → Extend the best previous subsequence.

1. Classic LIS — Very Common

Longest Increasing Subsequence

Two ways to find the longest subsequence of strictly increasing values — O(n²) DP and O(n log n) patience sorting.

dp[i] = 1 + max(dp[j] for j<i and nums[j]<nums[i]). For each element extend the best earlier increasing run. O(n²) time, O(n) space.

ARRAY VISUALIZER

Steps –

101

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i] = 1 for all i
                      
                        2
                        for i in 0..n-1:
                      
                        3
                          for j in 0..i-1:
                      
                        4
                            if nums[j] < nums[i]:
                      
                        5
                              dp[i] = max(dp[i], dp[j] + 1)
                      
                        6
                        return max(dp)

When to use

Use this pattern when:

The input is a sequence.
Elements may be skipped.
Relative order must be preserved.
You need the longest valid subsequence.
A previous element must satisfy a condition before extending the sequence.

Typical questions:

Longest Increasing Subsequence
Longest Decreasing Subsequence
Longest Non-Decreasing Subsequence

State

dp[i] =
length of the longest valid subsequence ending at index i

Transition

if nums[j] < nums[i]:

    dp[i] = max(dp[i], dp[j] + 1)

Java Template

public int lengthOfLIS(int[] nums) {
    int n = nums.length;

    if (n == 0) return 0;

    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

def length_of_lis(nums):
    n = len(nums)

    if n == 0:
        return 0

    dp = [1] * n

    answer = 1

    for i in range(n):
        for j in range(i):

            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

        answer = max(answer, dp[i])

    return answer

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();

    if (n == 0) return 0;

    vector<int> dp(n, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        answer = max(answer, dp[i]);
    }

    return answer;
}

function lengthOfLIS(nums) {
  const n = nums.length;

  if (n === 0) return 0;

  const dp = new Array(n).fill(1);

  let answer = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }

    answer = Math.max(answer, dp[i]);
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“Longest increasing subsequence” → dp[i] = best sequence ending at i.

2. LIS with Binary Search — Very Common

LIS via Binary Search

Maintain the smallest tail of all increasing runs of each length.

For each number, replace the first tail that is >= it (keep array sorted); if larger than all, append. The tail array length is the LIS. O(n log n) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        tails = []
                      
                        2
                        for x in nums:
                      
                        3
                          i = lower_bound(tails, x)
                      
                        4
                          tails[i] = x   // append if i == len
                      
                        5
                        return tails.length

The O(n²) solution can be optimized to O(n log n) when only the LIS length is required.

The important idea is that we do not store the actual LIS.

Instead:

tails[i] =
smallest possible ending value
of an increasing subsequence of length i + 1

A smaller tail gives us more opportunities to extend the subsequence later.

Java Template

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;

    for (int num : nums) {

        int left = 0;
        int right = size;

        // lower_bound:
        // first position where tails[pos] >= num
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (tails[mid] < num)
                left = mid + 1;
            else
                right = mid;
        }

        tails[left] = num;

        if (left == size)
            size++;
    }

    return size;
}

def length_of_lis(nums):
    tails = [0] * len(nums)
    size = 0

    for num in nums:
        left = 0
        right = size

        # lower_bound:
        # first position where tails[pos] >= num
        while left < right:
            mid = (left + right) // 2

            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid

        tails[left] = num

        if left == size:
            size += 1

    return size

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails(nums.size());
    int size = 0;

    for (int num : nums) {

        int left = 0;
        int right = size;

        // lower_bound:
        // first position where tails[pos] >= num
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (tails[mid] < num)
                left = mid + 1;
            else
                right = mid;
        }

        tails[left] = num;

        if (left == size)
            size++;
    }

    return size;
}

function lengthOfLIS(nums) {
  const tails = new Array(nums.length);

  let size = 0;

  for (const num of nums) {
    let left = 0;
    let right = size;

    // lower_bound:
    // first position where tails[pos] >= num
    while (left < right) {
      const mid = left + ((right - left) >> 1);

      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }

    tails[left] = num;

    if (left === size) size++;
  }

  return size;
}

Complexity

Time:  O(n log n)
Space: O(n)

Important

For strictly increasing LIS:

lower_bound

For non-decreasing LIS:

upper_bound

Mental Trigger

“LIS + large constraints + only length needed” → Binary Search LIS.

3. Maximum Sum Increasing Subsequence — Common

Maximum Sum Increasing Subsequence

Longest increasing subsequence that maximizes the sum of values.

Like LIS but dp[i] stores the max sum of an increasing subsequence ending at i: dp[i] = max(nums[i], max_{j<i, nums[j]<nums[i]} dp[j] + nums[i]). O(n²) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i] = nums[i]  // alone
                      
                        2
                        for i in 1..n:
                      
                        3
                          for j in 0..i:
                      
                        4
                            if nums[j] < nums[i]:
                      
                        5
                              dp[i] = max(dp[i], dp[j] + nums[i])
                      
                        6
                        return max(dp)

Here the objective changes.

Instead of:

maximize length

we want:

maximize sum

State

dp[i] =
maximum sum of an increasing subsequence
ending at i

Transition

if nums[j] < nums[i]:

    dp[i] = max(
        dp[i],
        dp[j] + nums[i]
    )

Java Template

public int maxSumIncreasingSubsequence(int[] nums) {
    int n = nums.length;

    if (n == 0) return 0;

    int[] dp = new int[n];

    int answer = 0;

    for (int i = 0; i < n; i++) {
        dp[i] = nums[i];

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                dp[i] = Math.max(
                    dp[i],
                    dp[j] + nums[i]
                );
            }
        }

        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

def max_sum_increasing_subsequence(nums):
    n = len(nums)

    if n == 0:
        return 0

    dp = [0] * n

    answer = 0

    for i in range(n):
        dp[i] = nums[i]

        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + nums[i])

        answer = max(answer, dp[i])

    return answer

int maxSumIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();

    if (n == 0) return 0;

    vector<int> dp(n);

    int answer = 0;

    for (int i = 0; i < n; i++) {
        dp[i] = nums[i];

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + nums[i]);
            }
        }

        answer = max(answer, dp[i]);
    }

    return answer;
}

function maxSumIncreasingSubsequence(nums) {
  const n = nums.length;

  if (n === 0) return 0;

  const dp = new Array(n).fill(0);

  let answer = 0;

  for (let i = 0; i < n; i++) {
    dp[i] = nums[i];

    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + nums[i]);
      }
    }

    answer = Math.max(answer, dp[i]);
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“LIS but maximize sum” → Replace length with sum.

4. Number of LIS — Common

Number of LIS

Count how many longest increasing subsequences exist.

Track two arrays: len[i] = LIS length ending at i, cnt[i] = number of such sequences. When extending j→i: if len[j]+1 > len[i], start fresh cnt=cnt[j]; if equal, add cnt[j]. O(n²) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        len[i] = 1, cnt[i] = 1
                      
                        2
                        for i in 1..n:
                      
                        3
                          for j in 0..i:
                      
                        4
                            if nums[j] < nums[i]:
                      
                        5
                              if len[j]+1 > len[i]: len[i]=len[j]+1; cnt[i]=cnt[j]
                      
                        6
                              elif len[j]+1 == len[i]: cnt[i] += cnt[j]
                      
                        7
                        return sum(cnt[i] where len[i]==maxLen)

Sometimes the question asks:

How many longest increasing subsequences exist?

We need to track two states.

length[i] =
LIS length ending at i

count[i] =
number of LIS of that length ending at i

Java Template

public int findNumberOfLIS(int[] nums) {
    int n = nums.length;

    if (n == 0) return 0;

    int[] length = new int[n];
    int[] count = new int[n];

    Arrays.fill(length, 1);
    Arrays.fill(count, 1);

    int maxLength = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {

                if (length[j] + 1 > length[i]) {

                    length[i] = length[j] + 1;
                    count[i] = count[j];

                } else if (length[j] + 1 == length[i]) {

                    count[i] += count[j];
                }
            }
        }

        maxLength = Math.max(maxLength, length[i]);
    }

    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (length[i] == maxLength) {
            answer += count[i];
        }
    }

    return answer;
}

def find_number_of_lis(nums):
    n = len(nums)

    if n == 0:
        return 0

    length = [1] * n
    count = [1] * n

    max_length = 1

    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:

                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]

        max_length = max(max_length, length[i])

    answer = 0

    for i in range(n):
        if length[i] == max_length:
            answer += count[i]

    return answer

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();

    if (n == 0) return 0;

    vector<int> length(n, 1);
    vector<int> count(n, 1);

    int maxLength = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {

                if (length[j] + 1 > length[i]) {

                    length[i] = length[j] + 1;
                    count[i] = count[j];

                } else if (length[j] + 1 == length[i]) {

                    count[i] += count[j];
                }
            }
        }

        maxLength = max(maxLength, length[i]);
    }

    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (length[i] == maxLength) {
            answer += count[i];
        }
    }

    return answer;
}

function findNumberOfLIS(nums) {
  const n = nums.length;

  if (n === 0) return 0;

  const length = new Array(n).fill(1);
  const count = new Array(n).fill(1);

  let maxLength = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        if (length[j] + 1 > length[i]) {
          length[i] = length[j] + 1;
          count[i] = count[j];
        } else if (length[j] + 1 === length[i]) {
          count[i] += count[j];
        }
      }
    }

    maxLength = Math.max(maxLength, length[i]);
  }

  let answer = 0;

  for (let i = 0; i < n; i++) {
    if (length[i] === maxLength) {
      answer += count[i];
    }
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“How many LIS?” → Track length + count.

5. Longest Bitonic Subsequence — Common

Longest Bitonic Subsequence

Sequence that increases then decreases (mountain shape).

Compute inc[i] = LIS ending at i and dec[i] = longest decreasing subsequence starting at i. Bitonic length at i = inc[i] + dec[i] - 1. Take the max. O(n²) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        inc[i] = LIS length ending at i
                      
                        2
                        dec[i] = LDS length starting at i
                      
                        3
                        for i in 0..n: best = max(best, inc[i] + dec[i] - 1)
                      
                        4
                        return best

A bitonic subsequence:

increasing → decreasing

We calculate two DP arrays.

lis[i] =
longest increasing subsequence ending at i

lds[i] =
longest decreasing subsequence starting at i

Then:

answer = lis[i] + lds[i] - 1

The -1 removes the duplicated peak.

Java Template

public int longestBitonicSubsequence(int[] nums) {
    int n = nums.length;

    if (n == 0) return 0;

    int[] lis = new int[n];
    int[] lds = new int[n];

    Arrays.fill(lis, 1);
    Arrays.fill(lds, 1);

    // LIS ending at i
    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                lis[i] = Math.max(
                    lis[i],
                    lis[j] + 1
                );
            }
        }
    }

    // LDS starting at i
    for (int i = n - 1; i >= 0; i--) {

        for (int j = n - 1; j > i; j--) {

            if (nums[j] < nums[i]) {
                lds[i] = Math.max(
                    lds[i],
                    lds[j] + 1
                );
            }
        }
    }

    int answer = 0;

    for (int i = 0; i < n; i++) {
        answer = Math.max(
            answer,
            lis[i] + lds[i] - 1
        );
    }

    return answer;
}

def longest_bitonic_subsequence(nums):
    n = len(nums)

    if n == 0:
        return 0

    lis = [1] * n
    lds = [1] * n

    # LIS ending at i
    for i in range(n):
        for j in range(i):

            if nums[j] < nums[i]:
                lis[i] = max(lis[i], lis[j] + 1)

    # LDS starting at i
    for i in range(n - 1, -1, -1):
        for j in range(n - 1, i, -1):

            if nums[j] < nums[i]:
                lds[i] = max(lds[i], lds[j] + 1)

    answer = 0

    for i in range(n):
        answer = max(answer, lis[i] + lds[i] - 1)

    return answer

int longestBitonicSubsequence(vector<int>& nums) {
    int n = nums.size();

    if (n == 0) return 0;

    vector<int> lis(n, 1);
    vector<int> lds(n, 1);

    // LIS ending at i
    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }

    // LDS starting at i
    for (int i = n - 1; i >= 0; i--) {

        for (int j = n - 1; j > i; j--) {

            if (nums[j] < nums[i]) {
                lds[i] = max(lds[i], lds[j] + 1);
            }
        }
    }

    int answer = 0;

    for (int i = 0; i < n; i++) {
        answer = max(answer, lis[i] + lds[i] - 1);
    }

    return answer;
}

function longestBitonicSubsequence(nums) {
  const n = nums.length;

  if (n === 0) return 0;

  const lis = new Array(n).fill(1);
  const lds = new Array(n).fill(1);

  // LIS ending at i
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        lis[i] = Math.max(lis[i], lis[j] + 1);
      }
    }
  }

  // LDS starting at i
  for (let i = n - 1; i >= 0; i--) {
    for (let j = n - 1; j > i; j--) {
      if (nums[j] < nums[i]) {
        lds[i] = Math.max(lds[i], lds[j] + 1);
      }
    }
  }

  let answer = 0;

  for (let i = 0; i < n; i++) {
    answer = Math.max(answer, lis[i] + lds[i] - 1);
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“Increase then decrease” → LIS from left + LDS from right.

6. Russian Doll Envelopes — Very Common Hidden LIS

Russian Doll Envelopes

Maximum number of envelopes you can nest inside each other.

Sort by width ascending, and by height DESCENDING when widths are equal. Then the answer is the LIS of heights (equal width can't nest, so desc height prevents counting them). O(n log n) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort envelopes by w asc, then h desc
                      
                        2
                        extract heights[]
                      
                        3
                        return LIS(heights)

Each envelope has:

width
height

An envelope can contain another only if both dimensions are strictly larger.

The trick is to convert the 2D problem into LIS.

Step 1

Sort:

width ascending
height descending when widths are equal

The descending height tie-break prevents envelopes with the same width from being included together.

Step 2

Run strict LIS on heights.

Java Template

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] != b[0]) {
            return Integer.compare(a[0], b[0]);
        }

        return Integer.compare(b[1], a[1]);
    });

    int[] tails = new int[envelopes.length];
    int size = 0;

    for (int[] envelope : envelopes) {

        int height = envelope[1];

        int left = 0;
        int right = size;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (tails[mid] < height)
                left = mid + 1;
            else
                right = mid;
        }

        tails[left] = height;

        if (left == size)
            size++;
    }

    return size;
}

def max_envelopes(envelopes):
    envelopes.sort(key=lambda e: (e[0], -e[1]))

    tails = [0] * len(envelopes)
    size = 0

    for envelope in envelopes:
        height = envelope[1]

        left = 0
        right = size

        while left < right:
            mid = (left + right) // 2

            if tails[mid] < height:
                left = mid + 1
            else:
                right = mid

        tails[left] = height

        if left == size:
            size += 1

    return size

int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(),
         [](const vector<int>& a, const vector<int>& b) {
             if (a[0] != b[0]) {
                 return a[0] < b[0];
             }

             return b[1] < a[1];
         });

    vector<int> tails(envelopes.size());
    int size = 0;

    for (auto& envelope : envelopes) {

        int height = envelope[1];

        int left = 0;
        int right = size;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (tails[mid] < height)
                left = mid + 1;
            else
                right = mid;
        }

        tails[left] = height;

        if (left == size)
            size++;
    }

    return size;
}

function maxEnvelopes(envelopes) {
  envelopes.sort((a, b) =>
    a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]
  );

  const tails = new Array(envelopes.length);

  let size = 0;

  for (const envelope of envelopes) {
    const height = envelope[1];

    let left = 0;
    let right = size;

    while (left < right) {
      const mid = left + ((right - left) >> 1);

      if (tails[mid] < height) left = mid + 1;
      else right = mid;
    }

    tails[left] = height;

    if (left === size) size++;
  }

  return size;
}

Complexity

Time:  O(n log n)
Space: O(n)

Mental Trigger

“2D nesting” → Sort one dimension → LIS on the other.

7. Largest Divisible Subset — Common

Largest Divisible Subset

Biggest subset where every pair divides.

Sort ascending. A new element can extend a subset if it is divisible by the subset's largest element. dp[i] = longest chain ending at i using the divisibility rule. O(n²) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort(nums)
                      
                        2
                        dp[i] = 1
                      
                        3
                        for i in 1..n:
                      
                        4
                          for j in 0..i:
                      
                        5
                            if nums[i] % nums[j] == 0:
                      
                        6
                              dp[i] = max(dp[i], dp[j] + 1)
                      
                        7
                        return max(dp)

This is LIS-style DP, but the compatibility condition changes.

Instead of:

nums[j] < nums[i]

we use:

nums[i] % nums[j] == 0

Sort first so that divisibility can be built from smaller values.

Java Template

public List<Integer> largestDivisibleSubset(int[] nums) {
    int n = nums.length;

    if (n == 0) return new ArrayList<>();

    Arrays.sort(nums);

    int[] dp = new int[n];
    int[] parent = new int[n];

    Arrays.fill(dp, 1);
    Arrays.fill(parent, -1);

    int bestIndex = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[i] % nums[j] == 0 &&
                dp[j] + 1 > dp[i]) {

                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }

        if (dp[i] > dp[bestIndex]) {
            bestIndex = i;
        }
    }

    List<Integer> result = new ArrayList<>();

    while (bestIndex != -1) {
        result.add(nums[bestIndex]);
        bestIndex = parent[bestIndex];
    }

    Collections.reverse(result);

    return result;
}

def largest_divisible_subset(nums):
    n = len(nums)

    if n == 0:
        return []

    nums.sort()

    dp = [1] * n
    parent = [-1] * n

    best_index = 0

    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j

        if dp[i] > dp[best_index]:
            best_index = i

    result = []

    while best_index != -1:
        result.append(nums[best_index])
        best_index = parent[best_index]

    result.reverse()

    return result

vector<int> largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();

    if (n == 0) return {};

    sort(nums.begin(), nums.end());

    vector<int> dp(n, 1);
    vector<int> parent(n, -1);

    int bestIndex = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[i] % nums[j] == 0 &&
                dp[j] + 1 > dp[i]) {

                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }

        if (dp[i] > dp[bestIndex]) {
            bestIndex = i;
        }
    }

    vector<int> result;

    while (bestIndex != -1) {
        result.push_back(nums[bestIndex]);
        bestIndex = parent[bestIndex];
    }

    reverse(result.begin(), result.end());

    return result;
}

function largestDivisibleSubset(nums) {
  const n = nums.length;

  if (n === 0) return [];

  nums.sort((a, b) => a - b);

  const dp = new Array(n).fill(1);
  const parent = new Array(n).fill(-1);

  let bestIndex = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        parent[i] = j;
      }
    }

    if (dp[i] > dp[bestIndex]) {
      bestIndex = i;
    }
  }

  const result = [];

  while (bestIndex !== -1) {
    result.push(nums[bestIndex]);
    bestIndex = parent[bestIndex];
  }

  result.reverse();

  return result;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“Longest subset with a custom compatibility condition” → LIS-style DP.

8. Pair Chain — Common

Maximum Length Pair Chain

Longest chain of pairs where the next starts after the previous ends.

Sort pairs by their start (or end). Then it becomes an LIS-style DP on the end values: dp[i] = max chain length ending at pair i. O(n²) time (or O(n log n) greedy by end).

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort(pairs by start)
                      
                        2
                        dp[i] = 1
                      
                        3
                        for i in 1..n:
                      
                        4
                          for j in 0..i:
                      
                        5
                            if pairs[j].end <= pairs[i].start:
                      
                        6
                              dp[i] = max(dp[i], dp[j] + 1)
                      
                        7
                        return max(dp)

Each pair:

[a, b]

can be followed by:

[c, d]

when:

b < c

This can be solved using either:

Greedy sorting by second value
LIS-style DP

For a general LIS pattern, use DP.

Java Template

public int findLongestChain(int[][] pairs) {
    Arrays.sort(
        pairs,
        Comparator.comparingInt(a -> a[0])
    );

    int n = pairs.length;

    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = Math.max(
                    dp[i],
                    dp[j] + 1
                );
            }
        }

        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

def find_longest_chain(pairs):
    pairs.sort(key=lambda p: p[0])

    n = len(pairs)

    dp = [1] * n

    answer = 1

    for i in range(n):
        for j in range(i):
            if pairs[j][1] < pairs[i][0]:
                dp[i] = max(dp[i], dp[j] + 1)

        answer = max(answer, dp[i])

    return answer

int findLongestChain(vector<vector<int>>& pairs) {
    sort(pairs.begin(), pairs.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[0] < b[0];
         });

    int n = pairs.size();

    vector<int> dp(n, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        answer = max(answer, dp[i]);
    }

    return answer;
}

function findLongestChain(pairs) {
  pairs.sort((a, b) => a[0] - b[0]);

  const n = pairs.length;

  const dp = new Array(n).fill(1);

  let answer = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (pairs[j][1] < pairs[i][0]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }

    answer = Math.max(answer, dp[i]);
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Important

Pair Chain also has an optimal greedy solution:

Sort by ending value
→ choose earliest ending compatible pair

So this problem can connect LIS + Greedy patterns.

Mental Trigger

“Longest chain” → Sort → Define compatibility → LIS-style DP.

9. Box Stacking — Moderate

Box Stacking

Maximum height by stacking boxes (smaller base on larger base).

Generate all rotations, sort by base area descending. Then LIS-style DP on height where a box can sit on another only if both base dimensions are strictly smaller. O(n²) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        rotations = all 3 rotations per box
                      
                        2
                        sort by base area desc
                      
                        3
                        dp[i] = height[i]
                      
                        4
                        for i in 1..n:
                      
                        5
                          for j in 0..i:
                      
                        6
                            if base[j] > base[i]: dp[i] = max(dp[i], dp[j] + height[i])
                      
                        7
                        return max(dp)

Box stacking is a multidimensional LIS problem.

A box can be placed on another when its base dimensions are smaller.

Usually, rotations are allowed, so each box can generate multiple orientations.

Java Template

static class Box {
    int h;
    int w;
    int d;

    Box(int h, int w, int d) {
        this.h = h;
        this.w = w;
        this.d = d;
    }
}

public int maxStackHeight(int[][] boxes) {

    List<Box> all = new ArrayList<>();

    for (int[] box : boxes) {

        int a = box[0];
        int b = box[1];
        int c = box[2];

        addBox(all, a, b, c);
        addBox(all, b, a, c);
        addBox(all, c, a, b);
    }

    all.sort((x, y) ->
        Integer.compare(
            y.w * y.d,
            x.w * x.d
        )
    );

    int n = all.size();

    int[] dp = new int[n];

    int answer = 0;

    for (int i = 0; i < n; i++) {

        dp[i] = all.get(i).h;

        for (int j = 0; j < i; j++) {

            Box top = all.get(i);
            Box bottom = all.get(j);

            if (top.w < bottom.w &&
                top.d < bottom.d) {

                dp[i] = Math.max(
                    dp[i],
                    dp[j] + top.h
                );
            }
        }

        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

private void addBox(
    List<Box> boxes,
    int h,
    int a,
    int b
) {
    int w = Math.max(a, b);
    int d = Math.min(a, b);

    boxes.add(new Box(h, w, d));
}

class Box:
    def __init__(self, h, w, d):
        self.h = h
        self.w = w
        self.d = d

def max_stack_height(boxes):
    all_boxes = []

    for box in boxes:
        a = box[0]
        b = box[1]
        c = box[2]

        add_box(all_boxes, a, b, c)
        add_box(all_boxes, b, a, c)
        add_box(all_boxes, c, a, b)

    all_boxes.sort(key=lambda x: x.w * x.d, reverse=True)

    n = len(all_boxes)

    dp = [0] * n

    answer = 0

    for i in range(n):
        dp[i] = all_boxes[i].h

        for j in range(i):
            top = all_boxes[i]
            bottom = all_boxes[j]

            if top.w < bottom.w and top.d < bottom.d:
                dp[i] = max(dp[i], dp[j] + top.h)

        answer = max(answer, dp[i])

    return answer

def add_box(boxes, h, a, b):
    w = max(a, b)
    d = min(a, b)

    boxes.append(Box(h, w, d))

struct Box {
    int h;
    int w;
    int d;

    Box(int h_, int w_, int d_)
        : h(h_), w(w_), d(d_) {}
};

void addBox(vector<Box>& boxes, int h, int a, int b) {
    boxes.push_back(Box(h, max(a, b), min(a, b)));
}

int maxStackHeight(vector<vector<int>>& input) {
    vector<Box> all;

    for (auto& box : input) {

        int a = box[0];
        int b = box[1];
        int c = box[2];

        addBox(all, a, b, c);
        addBox(all, b, a, c);
        addBox(all, c, a, b);
    }

    sort(all.begin(), all.end(),
         [](const Box& x, const Box& y) {
             return x.w * x.d > y.w * y.d;
         });

    int n = all.size();

    vector<int> dp(n);

    int answer = 0;

    for (int i = 0; i < n; i++) {

        dp[i] = all[i].h;

        for (int j = 0; j < i; j++) {

            const Box& top = all[i];
            const Box& bottom = all[j];

            if (top.w < bottom.w &&
                top.d < bottom.d) {

                dp[i] = max(dp[i], dp[j] + top.h);
            }
        }

        answer = max(answer, dp[i]);
    }

    return answer;
}

class Box {
  constructor(h, w, d) {
    this.h = h;
    this.w = w;
    this.d = d;
  }
}

function addBox(boxes, h, a, b) {
  const w = Math.max(a, b);
  const d = Math.min(a, b);

  boxes.push(new Box(h, w, d));
}

function maxStackHeight(boxes) {
  const all = [];

  for (const box of boxes) {
    const a = box[0];
    const b = box[1];
    const c = box[2];

    addBox(all, a, b, c);
    addBox(all, b, a, c);
    addBox(all, c, a, b);
  }

  all.sort((x, y) => y.w * y.d - x.w * x.d);

  const n = all.length;

  const dp = new Array(n).fill(0);

  let answer = 0;

  for (let i = 0; i < n; i++) {
    dp[i] = all[i].h;

    for (let j = 0; j < i; j++) {
      const top = all[i];
      const bottom = all[j];

      if (top.w < bottom.w && top.d < bottom.d) {
        dp[i] = Math.max(dp[i], dp[j] + top.h);
      }
    }

    answer = Math.max(answer, dp[i]);
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“Stack objects using multiple dimensions” → Sort dimensions + LIS-style DP.

10. Building Bridges — Moderate

Building Bridges

Maximum non-crossing bridges between two banks.

Sort bridges by the north-bank city. The problem reduces to the LIS of south-bank cities (crossing bridges would break increasing order). O(n log n) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort bridges by north city
                      
                        2
                        south[] = south-bank cities in that order
                      
                        3
                        return LIS(south)

Each bridge connects two sides.

We want the maximum number of bridges without crossings.

The common transformation is:

Sort by one coordinate
→ LIS on the other coordinate

Java Template

public int maxBridges(int[][] bridges) {

    Arrays.sort(bridges, (a, b) -> {
        if (a[0] != b[0]) {
            return Integer.compare(a[0], b[0]);
        }

        return Integer.compare(a[1], b[1]);
    });

    int n = bridges.length;

    int[] dp = new int[n];

    Arrays.fill(dp, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (bridges[j][1] < bridges[i][1]) {

                dp[i] = Math.max(
                    dp[i],
                    dp[j] + 1
                );
            }
        }

        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

def max_bridges(bridges):
    bridges.sort(key=lambda b: (b[0], b[1]))

    n = len(bridges)

    dp = [1] * n

    answer = 1

    for i in range(n):
        for j in range(i):
            if bridges[j][1] < bridges[i][1]:
                dp[i] = max(dp[i], dp[j] + 1)

        answer = max(answer, dp[i])

    return answer

int maxBridges(vector<vector<int>>& bridges) {
    sort(bridges.begin(), bridges.end(),
         [](const vector<int>& a, const vector<int>& b) {
             if (a[0] != b[0]) {
                 return a[0] < b[0];
             }

             return a[1] < b[1];
         });

    int n = bridges.size();

    vector<int> dp(n, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (bridges[j][1] < bridges[i][1]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        answer = max(answer, dp[i]);
    }

    return answer;
}

function maxBridges(bridges) {
  bridges.sort((a, b) =>
    a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]
  );

  const n = bridges.length;

  const dp = new Array(n).fill(1);

  let answer = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (bridges[j][1] < bridges[i][1]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }

    answer = Math.max(answer, dp[i]);
  }

  return answer;
}

Complexity

Time:  O(n²)
Space: O(n)

Mental Trigger

“Non-crossing connections” → Sort one side + LIS on the other.

How LIS Variants Change

Most LIS problems use the same basic structure.

The part that changes is the compatibility condition and the objective.

Standard LIS

if (nums[j] < nums[i])
    dp[i] = Math.max(dp[i], dp[j] + 1);

Maximum Sum LIS

if (nums[j] < nums[i])
    dp[i] = Math.max(dp[i], dp[j] + nums[i]);

Divisible Subset

if (nums[i] % nums[j] == 0)
    dp[i] = Math.max(dp[i], dp[j] + 1);

Pair Chain

if (pairs[j][1] < pairs[i][0])
    dp[i] = Math.max(dp[i], dp[j] + 1);

The Pattern

Define dp[i]
      ↓
Find compatible j
      ↓
Extend dp[j]
      ↓
Take best answer

General LIS Java Template

For most O(n²) LIS-style problems:

public int lisTemplate(int[] nums) {
    int n = nums.length;

    if (n == 0) return 0;

    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (isCompatible(nums[j], nums[i])) {
                dp[i] = Math.max(
                    dp[i],
                    dp[j] + 1
                );
            }
        }

        answer = Math.max(answer, dp[i]);
    }

    return answer;
}

private boolean isCompatible(int previous, int current) {
    return previous < current;
}

def lis_template(nums):
    n = len(nums)

    if n == 0:
        return 0

    dp = [1] * n

    answer = 1

    for i in range(n):
        for j in range(i):
            if is_compatible(nums[j], nums[i]):
                dp[i] = max(dp[i], dp[j] + 1)

        answer = max(answer, dp[i])

    return answer

def is_compatible(previous, current):
    return previous < current

bool isCompatible(int previous, int current) {
    return previous < current;
}

int lisTemplate(vector<int>& nums) {
    int n = nums.size();

    if (n == 0) return 0;

    vector<int> dp(n, 1);

    int answer = 1;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (isCompatible(nums[j], nums[i])) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        answer = max(answer, dp[i]);
    }

    return answer;
}

function isCompatible(previous, current) {
  return previous < current;
}

function lisTemplate(nums) {
  const n = nums.length;

  if (n === 0) return 0;

  const dp = new Array(n).fill(1);

  let answer = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (isCompatible(nums[j], nums[i])) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }

    answer = Math.max(answer, dp[i]);
  }

  return answer;
}

The important part is:

isCompatible(...)

This changes depending on the problem.

LIS Reconstruction Template

If the problem asks for the actual subsequence, not just its length, maintain a parent array.

public List<Integer> reconstructLIS(int[] nums) {
    int n = nums.length;

    int[] dp = new int[n];
    int[] parent = new int[n];

    Arrays.fill(dp, 1);
    Arrays.fill(parent, -1);

    int bestIndex = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i] &&
                dp[j] + 1 > dp[i]) {

                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }

        if (dp[i] > dp[bestIndex]) {
            bestIndex = i;
        }
    }

    List<Integer> result = new ArrayList<>();

    while (bestIndex != -1) {
        result.add(nums[bestIndex]);
        bestIndex = parent[bestIndex];
    }

    Collections.reverse(result);

    return result;
}

def reconstruct_lis(nums):
    n = len(nums)

    dp = [1] * n
    parent = [-1] * n

    best_index = 0

    for i in range(n):
        for j in range(i):

            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j

        if dp[i] > dp[best_index]:
            best_index = i

    result = []

    while best_index != -1:
        result.append(nums[best_index])
        best_index = parent[best_index]

    result.reverse()

    return result

vector<int> reconstructLIS(vector<int>& nums) {
    int n = nums.size();

    vector<int> dp(n, 1);
    vector<int> parent(n, -1);

    int bestIndex = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i] &&
                dp[j] + 1 > dp[i]) {

                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }

        if (dp[i] > dp[bestIndex]) {
            bestIndex = i;
        }
    }

    vector<int> result;

    while (bestIndex != -1) {
        result.push_back(nums[bestIndex]);
        bestIndex = parent[bestIndex];
    }

    reverse(result.begin(), result.end());

    return result;
}

function reconstructLIS(nums) {
  const n = nums.length;

  const dp = new Array(n).fill(1);
  const parent = new Array(n).fill(-1);

  let bestIndex = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        parent[i] = j;
      }
    }

    if (dp[i] > dp[bestIndex]) {
      bestIndex = i;
    }
  }

  const result = [];

  while (bestIndex !== -1) {
    result.push(nums[bestIndex]);
    bestIndex = parent[bestIndex];
  }

  result.reverse();

  return result;
}

Mental Trigger

“Need the actual LIS” → Add parent[] and reconstruct backwards.

How to Identify LIS Problems

Ask:

Is this a sequence or ordered collection?
Can I skip elements?
Must relative order be preserved?
Is there a compatibility condition between two elements?
Am I maximizing length, sum, or count?
Can sorting reduce a multidimensional problem to LIS?

If most answers are yes:

Think LIS-style DP.

Common Mistakes

Confusing subsequence with subarray

Subsequence:

[1, 3, 5]

can skip elements.

Subarray must be contiguous.

[1, 2, 3]

Using `<=` for strict LIS

Strictly increasing:

nums[j] < nums[i]

Non-decreasing:

nums[j] <= nums[i]

Forgetting tie-breaking after sorting

For multidimensional LIS problems, sorting ties incorrectly can create invalid sequences.

Example:

Russian Doll Envelopes

requires:

width ascending
height descending for equal width

Using Binary Search LIS when reconstruction is required

The tails method gives the LIS length efficiently, but reconstructing the actual sequence requires additional parent/index tracking.

Forgetting the peak duplication in Bitonic DP

Use:

LIS[i] + LDS[i] - 1

not:

LIS[i] + LDS[i]

Recognition Cheat Sheet

If you see…	Think…
Longest increasing subsequence	Classic LIS
Large `n` + LIS length	Binary Search LIS
Increasing + maximum sum	Maximum Sum LIS
Count all longest subsequences	Number of LIS
Increase then decrease	Bitonic DP
Nested envelopes	Sort + LIS
Divisibility chain	Divisible Subset DP
Longest valid pair chain	Pair Chain
Stack objects by dimensions	Multi-dimensional LIS
Non-crossing connections	Sort + LIS

Complexity Cheat Sheet

Pattern	Time	Space
Classic LIS	O(n²)	O(n)
Binary Search LIS	O(n log n)	O(n)
Maximum Sum LIS	O(n²)	O(n)
Number of LIS	O(n²)	O(n)
Bitonic Subsequence	O(n²)	O(n)
Russian Doll Envelopes	O(n log n)	O(n)
Divisible Subset	O(n²)	O(n)
Pair Chain DP	O(n²)	O(n)
Box Stacking	O(n²)	O(n)
Building Bridges	O(n²)	O(n)

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Classic LIS — Very Common

Longest Increasing Subsequence

When to use

State

Transition

Java Template

Complexity

Mental Trigger

2. LIS with Binary Search — Very Common

LIS via Binary Search

Java Template

Complexity

Important

Mental Trigger

3. Maximum Sum Increasing Subsequence — Common

Maximum Sum Increasing Subsequence

State

Transition

Java Template

Complexity

Mental Trigger

4. Number of LIS — Common

Number of LIS

Java Template

Complexity

Mental Trigger

5. Longest Bitonic Subsequence — Common

Longest Bitonic Subsequence

Java Template

Complexity

Mental Trigger

6. Russian Doll Envelopes — Very Common Hidden LIS

Russian Doll Envelopes

Step 1

Step 2

Java Template

Complexity

Mental Trigger

7. Largest Divisible Subset — Common

Largest Divisible Subset

Java Template

Complexity

Mental Trigger

8. Pair Chain — Common

Maximum Length Pair Chain

Java Template

Complexity

Important

Mental Trigger

9. Box Stacking — Moderate

Box Stacking

Java Template

Complexity

Mental Trigger

10. Building Bridges — Moderate

Building Bridges

Java Template

Complexity

Mental Trigger

How LIS Variants Change

Standard LIS

Maximum Sum LIS

Divisible Subset

Pair Chain

The Pattern

General LIS Java Template

LIS Reconstruction Template

Mental Trigger

How to Identify LIS Problems

Common Mistakes

Confusing subsequence with subarray

Using <= for strict LIS

Forgetting tie-breaking after sorting

Using Binary Search LIS when reconstruction is required

Forgetting the peak duplication in Bitonic DP

Recognition Cheat Sheet

Complexity Cheat Sheet

Using `<=` for strict LIS