จำนวน Longest Increasing Subsequences ทั้งหมดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข arr เป็นอาร์กิวเมนต์เดียว

ฟังก์ชันต้องหาจำนวนของ longest increasing subsequences (ติดกันหรือไม่ติดกันก็ได้)

ตัวอย่างเช่น หากอินพุตคือ

Input

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

Output

const output = 2;

คำอธิบายผลลัพธ์

LIS สองอันคือ [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