Leetcode 日記: 53. 最大サブアレイ

これは新しいシリーズで、リートコードの質問に苦戦している様子を記録しています.たとえ少数の聴衆であっても、継続するモチベーションを与えてくれることを願っています.

link

ああ、クラシック!これはおそらく、リートコードで最初に直面する問題の 1 つであり、すべてのプログラマーが自分たちが地獄のような業界にいることに気付くようになります.これを初めて見たとき、どうやって解決するつもりなの?!?!?!?!??わかりません、確かではありませんでしたが、今日ここにあるこの記事の何かが、これをよりよく理解するのに役立つことを願っています.

問題は、合計が最大になる部分配列を見つけることです.インデックスから開始し、すべてのインデックスを追加した後に合計を見つけるというブルートフォースを介して行うことができます.

let max = -Infinity;
for (let i=0; i<nums.length; i++) {
    let sum = nums[i];
    for (let j=i+1; j<nums.length; j++) {
        sum+= nums[j];
        max = Math.max(sum)
    }
}

O(N ^ 2)で問題なく動作することを除いて、これは確かに答えを得るでしょう.あなたはもっとうまくやることができます.

配列をソートすることはできないため、間違いなく NlogN ソリューションではありません.検索は機能しません...コンテキストで意味をなさないだけです.

したがって、O(N) アプローチ、つまり反復が残されます.

[1,2,3,4,5,6,67,8,9,10] の場合、現在の合計に追加して最大値を更新し続けるだけです.簡単ピーシーレモンスクイーズ.

[1,-2,-3,-4,-5,-6,-8] の場合、合計は小さくなり続けますが、同じ単純なアプローチを実行して同じ答えを得ることができます.

興味深いのは、2 つのケースを組み合わせるとどうなるかということです.
[1,2,3,4,5,6,67,8,9,10,1,-2,-3,-4,-5,-6,-8]
この場合...何も変更する必要はありませんよね?ただし、現在の合計に単純に追加して最大値をチェックすることは引き続き機能します...

[1,-2,-3,-4,-5,-6,-8, 777, 2,3,4,5,6,67,8,9,10]
それでは、繰り返しながら合計を追加し続けますか?明白な答えは、777 に出くわしたとき、以前に起こったことを「無視」して、新たに始めることです.言い換えれば、1 つの配列を 2 つの異なる配列であるかのように扱うことを除いて、素朴なアプローチを実行しているだけです.

問題は、いつリセットするかです. 777 アレイに戻りましょう.なぜ 777 より前を無視するのですか?それ以前の合計は役に立たないからですよね?彼らは合計を大きくするのではなく、小さくしているのに、なぜそれらを維持するのですか?答えは次のとおりです.
(sum+current_number) が current_number 自体よりも小さい場合は、合計をリセットします

以下の完全なコード:

var maxSubArray = function(nums) {
    let max = Number.MIN_SAFE_INTEGER;
    let curr = 0;
    nums.forEach(function(num){
        curr = num > curr+num ? num : curr + num;
        max = Math.max(max, curr);
    });

    return max;
};

解決策を見ずにこれを思い付くことができなくても、気にしないでください.これを初めて読んだ人は誰もいないと思います.ここでの教訓は、実際にはアルゴリズム自体ではありません.これはおそらく、これを使用する唯一の問題だからです.ここでのレッスンは、プロセスに関するものです.

問題に行き詰まったら、考えられるすべてのシナリオを試してください.私たちは、すべての正の整数に対して明らかに機能する単純なアプローチから始めました.次の直感的なことは、すべての負の整数に対してまだ機能するかどうかを確認することです.それは素晴らしいです!私たちはそれを難し​​くし、それがポジティブだったらネガティブだったらどうなるかを想像します.コードは今でも驚くほど機能します.最後に、ネガティブ、次にポジティブを見ていきます.コードが機能しないため、かなりうまく機能しているため、コードを少し変更する必要があります.

正直なところ、あなたがこの問題に直面したことがなく、ここまで来たのであれば、たとえ解決策が間に合わなくても、私があなたの面接官だったとしても問題ありません.あなたは明らかにリートコードをあまり行っていませんが、分析に関しては非常に系統的で体系的でした.それだけでも十分に印象的です.個別の数学コースに苦しむまで、私はこのように考える方法を学びませんでした...呪い、そして私の教授に感謝します:( ...

これを読んだ後、あなたの心に何か教えてください、ありがとう!