Maximum Subarray

部分配列とは、リストの要素が途切れることなく並んだ連続部分です。整数のリストに含まれる空でないすべての部分配列のうち、要素の合計が最大になるものを見つけ、その合計を返します。

[2, -4, 3, -1, 5, -6, 1]では、最適な連続部分は[3, -1, 5]で、合計は7です。その後に続く5が-1の損失を十分に補うため、-1を含めます。一方、先頭の2は、その後の-4による損失のほうが2のもたらす利益より大きいため、含めません。

古典的な1回の走査で解く方法はKadane's algorithmです。リストを順に見て、現在の要素で終わる連続部分の合計の最大値を保持します。各要素では、前の要素で終わった連続部分を延長するか、ここから始まる新しい連続部分で再開するかの2つの選択肢しかありません。前の連続部分の合計が正の間だけ延長する価値があります。その合計が0以下になったら、引き継いでも不利になるだけなので、最初から始めます。答えは、途中で得られた連続部分の合計の最大値です。

この例では、各位置で終わる連続部分の合計の最大値は、2、-2、3、2、7、1、2となるため、答えは7です。各要素を1回ずつ見るので、処理量はリストの長さに対して線形に増加します。

整数のリスト nums を受け取り、nums の空でない連続部分配列の最大の合計を返す、maxSubArray という名前の関数を書いてください。

制約: 1 ≤ nums.length ≤ 10^5、-10^4 ≤ nums[i] ≤ 10^4。