Maximum Subarray

المصفوفة الفرعية هي مجموعة متتابعة من العناصر المتجاورة في قائمة، مأخوذة من دون فجوات. من بين جميع المصفوفات الفرعية غير الفارغة لقائمة من الأعداد الصحيحة، تريد اختيار المصفوفة التي يكون مجموع عناصرها أكبر ما يمكن، وتُعيد ذلك المجموع.

في [2, -4, 3, -1, 5, -6, 1]، أفضل مجموعة متتابعة هي [3, -1, 5]، ومجموعها 7. فهي تُبقي على -1 لأن 5 الذي يأتي بعده يعوّضه بأكثر من قيمته، وتستبعد 2 في البداية لأن -4 الذي يليه تكلفته أكبر مما يضيفه العدد 2.

الحل الكلاسيكي بمرور واحد هو خوارزمية Kadane. مرّ على القائمة واحتفظ بأكبر مجموع لمجموعة متتابعة تنتهي عند العنصر الحالي. عند كل عنصر، لديك خياران فقط: تمديد المجموعة المتتابعة التي انتهت عند العنصر السابق، أو البدء من جديد بمجموعة جديدة تبدأ هنا. لا يكون التمديد مجديًا إلا عندما يكون مجموع المجموعة السابقة موجبًا؛ فبمجرد أن يصبح ذلك المجموع صفرًا أو أقل، لا يمكن أن تؤدي مواصلته إلا إلى نتيجة أسوأ، لذا تبدأ من جديد. الإجابة هي أكبر مجموع لمجموعة متتابعة تصادفه في أي موضع أثناء المرور.

في هذا المثال، أكبر المجاميع للمجموعات المتتابعة المنتهية عند كل موضع هي 2 و-2 و3 و2 و7 و1 و2، لذا فالإجابة هي 7. يُفحَص كل عنصر مرة واحدة، لذا يزداد مقدار العمل خطيًا مع طول القائمة.

اكتب دالة باسم maxSubArray تستقبل قائمة من الأعداد الصحيحة nums وتُرجع أكبر مجموع لمصفوفة فرعية متصلة وغير فارغة من nums.

القيود: 1 ≤ nums.length ≤ 10^5، -10^4 ≤ nums[i] ≤ 10^4.