Maximum Subarray

Bir alt dizi, bir listedeki aralarında boşluk bulunmayan ardışık öğeler dizisidir. Bir tam sayı listesinin boş olmayan tüm alt dizileri arasından, öğelerinin toplamı en yüksek olanı bulmak ve bu toplamı döndürmek istersin.

[2, -4, 3, -1, 5, -6, 1] içinde en iyi dizi [3, -1, 5] olur ve toplamı 7'dir. -1 değerini içerir çünkü ardından gelen 5 bu değerin maliyetini fazlasıyla karşılar; baştaki 2 değerini ise dışarıda bırakır çünkü ardından gelen -4, 2'nin getirdiğinden daha fazlasına mal olur.

Klasik tek geçişli çözüm Kadane algoritmasıdır. Liste boyunca ilerle ve mevcut öğede sona eren bir dizinin en iyi toplamını tut. Her öğede yalnızca iki seçeneğin vardır: önceki öğede sona eren diziyi genişletmek veya burada başlayan yeni bir diziyle yeniden başlamak. Genişletmek, yalnızca önceki dizinin toplamı pozitif olduğu sürece işe yarar; bu toplam sıfıra veya altına düştüğünde onu taşımaya devam etmek yalnızca zarar verebilir, bu yüzden baştan başlarsın. Yanıt, ilerlerken karşılaşılan en büyük dizi toplamıdır.

Örnekte, her konumda sona eren en iyi dizi toplamları 2, -2, 3, 2, 7, 1 ve 2'dir; dolayısıyla yanıt 7'dir. Her öğe bir kez incelenir, bu nedenle işlem miktarı listenin uzunluğuyla doğrusal olarak artar.

maxSubArray adlı, bir tam sayı listesi nums alan ve nums içindeki bitişik, boş olmayan bir alt dizinin en büyük toplamını döndüren bir fonksiyon yazın.

Kısıtlamalar: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.