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.