인프런 커뮤니티 질문&답변

const main = (n) => {
  const memo = {};

  for (let i = 0; i < n.length; i++) {
    const biggerThanCur = Object.keys(memo).find((key) => n[i] > key);
    if (!biggerThanCur) memo[n[i]] = dfs(i, 0);
  }

  function dfs(index, count, recent = 0) {
    if (index === n.length) {
      return count;
    }

    if (n[index] > recent) {
      count++;
      recent = n[index];
    }

    return dfs(index + 1, count, recent);
  }

  let result = 0;
  for (const key in memo) {
    if (result < memo[key]) {
      result = memo[key];
    }
  }

  return result;
};

console.log(main([5, 3, 7, 8, 6, 2, 9, 4]));