Maximum Subarray Sum

# Maximum Subarray Sum ## Difficulty Medium ## Tags `array`, `dynamic programming`, `divide and conquer` ## Problem Statement Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. ## Constraints - 1 ≤ nums.length ≤ 10⁵ - -10⁴ ≤ nums[i] ≤ 10⁴ - The array can contain positive and negative integers. - Time complexity should be O(N). ## Signatures ### Python ```python def max_sub_array(nums: List[int]) -> int: pass ``` ### Java ```java public class Solution { public int max_sub_array(List<Integer> nums) { return null; } } ``` ### Csharp ```csharp public class Solution { public int max_sub_array(IList<int> nums) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int max_sub_array(vector<int> nums) { } }; ``` ### C ```c int max_sub_array(int* nums) { } ``` ### Ruby ```ruby def max_sub_array(nums) end ``` ### Perl ```perl sub max_sub_array { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def max_sub_array(nums: List[Int]): Int = { } } ``` ### Haskell ```haskell max_sub_array :: ... -> ... max_sub_array args = undefined ``` ### Clojure ```clojure (defn max_sub_array [nums] ) ``` ### Scheme ```scheme (define (max_sub_array nums) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] ``` **Output:** ``` 6 ``` **Explanation:** The subarray [4, -1, 2, 1] has the largest sum = 6. ### Example 2 **Input:** ``` nums = [1] ``` **Output:** ``` 1 ``` **Explanation:** Single element subarray. ### Example 3 **Input:** ``` nums = [5, 4, -1, 7, 8] ``` **Output:** ``` 23 ``` **Explanation:** The entire array has the largest sum. ### Example 4 **Input:** ``` nums = [-1, -2, -3] ``` **Output:** ``` -1 ``` **Explanation:** The least negative element is the best choice. ## Hints 1. Use Kadane's Algorithm. 2. Maintain a running sum of the current subarray. 3. If the running sum becomes negative, reset it (start a new subarray). 4. Track the maximum sum seen so far.