Longest Increasing Subsequence

subsequencepatience-sortordering

Press play to start

1function lis(arr: number[]): number {
const dp = Array(arr.length).fill(1)
for (let i = 1; i < arr.length; i++) {
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i])
      dp[i] = Math.max(dp[i], dp[j] + 1)
  }
}
return Math.max(...dp)
10}

Step 1/0

Custom array:

Complexity

Best:O(n²)
Average:O(n²)
Worst:O(n²)
Space:O(n)

Description

Finds the longest subsequence of a sequence in which the elements are in strictly increasing order.

When to use

Patience sorting, stock trading problems, chain problems, patience game analysis.