最大のサブ配列
入力は数値の配列です。e.g. arr = [1, -2, 3, 4, -9, 6].
タスクは次の通りです: アイテムの最大合計で arr の連続した部分配列を探します。
そのような返却をする関数 getMaxSubSum(arr) を書いてください。
例えば:
getMaxSubSum([-1, 2, 3, -9]) = 5 (ハイライトされたアイテムの合計)
getMaxSubSum([2, -1, 2, 3, -9]) = 6
getMaxSubSum([-1, 2, 3, -9, 11]) = 11
getMaxSubSum([-2, -1, 1, 2]) = 3
getMaxSubSum([100, -9, 2, -3, 5]) = 100
getMaxSubSum([1, 2, 3]) = 6 (すべて)もしすべてのアイテムが負値の場合、何も取らないことを意味します(サブ配列は空)、なので合計はゼロです:
getMaxSubSum([-1, -2, -3]) = 0早い解法を考えてみてください。: 可能なら O(n2) もしくは O(n) です。
遅い解法
すべての可能性のあるサブ合計を計算することができます。
最もシンプルな方法はすべての要素を取り、それから始まるすべてのサブ配列の合計を計算することです。
例えば、 [-1, 2, 3, -9, 11] に対しては:
// -1 から開始:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11
// 2 から開始:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11
// 3 から開始:
3
3 + (-9)
3 + (-9) + 11
// -9 から開始
-9
-9 + 11
// -11 から開始
-11コードは実際には入れ子のループです: 配列要素に対する外部ループ、および現在の要素で始まる内部カウントのサブ合計です。
function getMaxSubSum(arr) {
let maxSum = 0; // もし要素を取らない場合、ゼロが返却されます
for (let i = 0; i < arr.length; i++) {
let sumFixedStart = 0;
for (let j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Math.max(maxSum, sumFixedStart);
}
}
return maxSum;
}
alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100この解法は O(n2) の時間の複雑さを持っています。言い換えると、もし配列のサイズが2倍に増加すると、アルゴリズムは4倍長くなります。
大きな配列(1000, 10000 またはより多くのアイテム)に対しては、このようなアルゴリズムは深刻なレベルで低速になる可能性があります。
早い解法
配列を歩いて変数 s に現在の要素の部分合計を持ちましょう。s がある点で負になる場合は s=0 を代入します。このような s の最大値が答えになります。
説明にあまりピンとこない場合は、コードを参照してください、それは十分短いです:
function getMaxSubSum(arr) {
let maxSum = 0;
let partialSum = 0;
for (let item of arr) { // for each item of arr
partialSum += item; // add it to partialSum
maxSum = Math.max(maxSum, partialSum); // remember the maximum
if (partialSum < 0) partialSum = 0; // zero if negative
}
return maxSum;
}
alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0このアルゴリズムは1回の配列ループを必要とするので、時間複雑度は O(n) です。
あなたはここで、このアルゴリズムについてのより詳細な情報を見つけることができます: Maximum subarray problem. もしも、なぜそれが動作するのかがまだはっきりしていない場合は、上の例のアルゴリズムをトレースして、どのように動作するかを見てください。それはどんな言葉よりも優れています。
function getMaxSubSum(arr) {
let maxSum = 0;
let partialSum = 0;
for (let item of arr) {
partialSum += item;
maxSum = Math.max(maxSum, partialSum);
if (partialSum < 0) partialSum = 0;
}
return maxSum;
}