การลบสมาชิกน้อยที่สุดเพื่อทำให้อาร์เรย์เป็นลำดับเพิ่มขึ้นใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ตัวเลข ฟังก์ชันควรพยายามลบสมาชิกน้อยที่สุดจากอาร์เรย์ เพื่อให้อาร์เรย์กลายเป็นลำดับเพิ่มขึ้น (strictly increasing)

ตัวอย่าง

โค้ดตัวอย่างด้านล่าง:

const arr = [1, 100, 2, 3, 100, 4, 5];
const findIncreasingArray = (arr = []) => {
  const copy = arr.slice();
  for (let i = 0; i < copy.length; i++) {
    const el = arr[i];
    const next = arr[i + 1];
    if (el > next) {
      copy[i] = undefined;
    }
  }
  return copy.filter(Boolean);
};
console.log(findIncreasingArray(arr));

ผลลัพธ์

[ 1, 2, 3, 4, 5 ]

คำอธิบายเพิ่มเติม

โค้ดตัวอย่างมีข้อบกพร่อง: มันลบเฉพาะตัวที่มากกว่าตัวถัดไป ซึ่งไม่ได้แก้ปัญหา "ลบน้อยที่สุด" จริงๆ (Longest Increasing Subsequence) คำตอบที่ถูกต้องควรใช้ LIS algorithm (O(n log n)) เพื่อหาลำดับย่อยเพิ่มขึ้นที่ยาวที่สุด แล้วลบตัวอื่นออก