JavaScriptで配列を増加列に変換するために削除する要素数を最小化する方法

問題の概要

数字の配列を受け取り、残りの要素が左から右へ向かって値が増えていく「増加列」になるように、できるだけ少ない数の要素を削除する JavaScript 関数を作成します。

コード例

以下が実際のコードです。

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;
    }
  }

  // undefined を取り除いて結果を返す
  return copy.filter(Boolean);
};

console.log(findIncreasingArray(arr));

出力

[ 1, 2, 3, 4, 5 ]

コードの解説

処理の流れは以下のとおりです。

1. arr.slice() で元の配列をコピーし、元データが変更されないようにします。
2. for ループで隣り合う2つの要素を比較し、現在の要素が次の要素より大きい場合(= 数列が減少している箇所)、コピー内のその要素を undefined に置き換えます。
3. filter(Boolean) によって undefined などの falsy な値がすべて除外され、増加列だけが残ります。

この例では、値 100 が2か所(インデックス1と4)で直後の要素より大きくなっているため、これらの2要素が削除され、結果として [1, 2, 3, 4, 5] という増加列が得られます。

注意点：厳密な最小化について

この実装は隣接する要素同士しか比較しないシンプルな貪欲法のため、入力によっては数学的な意味での最小削除数にならないケースがあります。厳密な最適解が必要な場合は、「最長増加部分列(LIS: Longest Increasing Subsequence)」の長さを動的計画法で求め、配列の長さから引く(n − LISの長さ)ことで、本当に削除すべき最小要素数を正確に導くことができます。