JavaScript에서 가장 길게 증가하는 시퀀스의 총 수

문제

첫 번째이자 유일한 인수로 숫자 배열인 arr을 취하는 JavaScript 함수를 작성해야 합니다.

우리의 함수는 가장 길게 증가하는 부분 수열(연속 또는 비연속)의 수를 찾는 데 필요합니다.

예를 들어 함수에 대한 입력이

입력

const arr = [2, 4, 6, 5, 8];

출력

const output = 2;

출력 설명

두 개의 가장 긴 증가 부분 수열은 [2, 4, 5, 8] 및 [2, 4, 6, 8]입니다.

예시

다음은 코드입니다 -

const arr = [2, 4, 6, 5, 8];
const countSequence = (arr) => {
   const distance = new Array(arr.length).fill(1).map(() => 1)
   const count = new Array(arr.length).fill(1).map(() => 1)
   let max = 1
   for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
         if (arr[j] > arr[i]) {
            if (distance[j] <= distance[i]) {
               distance[j] = distance[i] + 1
               count[j] = count[i]
               max = Math.max(distance[j], max)
            } else if (distance[j] === distance[i] + 1) {
               count[j] += count[i]
            }
         }
      }
   }
   return distance.reduce((acc, d, index) => {
      if (d === max) {
         acc += count[index]
      }
      return acc
   }, 0)
}
console.log(countSequence(arr));

출력

2