Maior subsequência crescente

Solução 1 - DP O(n²)

Boa versão inicial porque deixa a recorrencia muito clara.

export function lengthOfLIS(nums: number[]): number {
  if (nums.length === 0) {
    return 0
  }

  const dp = new Array(nums.length).fill(1)
  let best = 1

  for (let index = 0; index < nums.length; index += 1) {
    for (let previous = 0; previous < index; previous += 1) {
      if (nums[previous] < nums[index]) {
        dp[index] = Math.max(dp[index], dp[previous] + 1)
      }
    }

    best = Math.max(best, dp[index])
  }

  return best
}

Funciona bem e ensina a regra.

Mas cada posição olha para todas as anteriores.

Solução 2 - Array de menores finais mais busca binaria

Agora a ideia não e guardar todas as respostas por indice.

E guardar o melhor final possível para cada comprimento.

export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = []

  for (const num of nums) {
    let left = 0
    let right = tails.length

    while (left < right) {
      const middle = Math.floor((left + right) / 2)

      if (tails[middle] < num) {
        left = middle + 1
      } else {
        right = middle
      }
    }

    tails[left] = num
  }

  return tails.length
}

O insight forte aqui e:

• o array de menores finais não e necessariamente a subsequencia final
• ele e a melhor fronteira para continuar crescendo

O que dizer na entrevista

Uma explicação curta e boa seria:

A versão inicial usa DP: dp[i] e a melhor subsequencia crescente terminando em i, entao eu testo todos os anteriores menores. A versão forte troca isso por um array de menores finais, muitas vezes chamado de tails, onde cada posição guarda o menor final possível para um certo comprimento. Com busca binaria eu descubro onde o número atual melhora essa fronteira e chego em O(n log n).

Isso mostra que você:

• entende primeiro a versão de DP
• sabe explicar por que o array de menores finais funciona
• não vende busca binaria como truque magico

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

• pensar em subsequencia e não em contiguidade
• guardar a melhor fronteira para o futuro
• combinar programação dinamica com busca binaria
• otimizar uma resposta O(n²) sem perder a intuição

O ponto não e decorar o nome tails.

O ponto e aprender a perguntar qual estado deixa mais espaco para crescer depois.