53. Maximum subarray sum

Given an integer array nums, find the subarray with the largest sum, and return its sum.

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: The subarray [1] has the largest sum 1.

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

    def maxSubArray(self, nums: List[int]) -> int:

        maxi = nums[0]
        sumof = 0
        
        for i in nums:
            sumof += i
            
            if sumof > maxi:
                maxi = sumof

            if sumof < 0:
                sumof = 0

        print(maxi)
        return maxi

Kadane's algorithm is a dynamic programming approach used to find the maximum subarray sum in a given array of numbers. The algorithm maintains two variables, current_sum and max_sum. It iterates through the array, updating current_sum by adding the current element or starting a new subarray if the current_sum becomes negative. The max_sum is updated whenever a higher current_sum is encountered.

Let's delve into it with an example:

Consider the array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

1. Initialization:

   • Set current_sum and max_sum to the first element: -2.

2. Iterate through the array:

   • At index 1, update current_sum to 1 (ignoring -2 as it doesn't contribute positively).
   • At index 2, update current_sum to -2 (1 - 3).
   • At index 3, reset current_sum to 4 (starting a new subarray).
   • At index 4, update current_sum to 3 (4 - 1).
   • At index 5, update current_sum to 5 (3 + 2).
   • At index 6, update current_sum to 6 (5 + 1).
   • At index 7, update current_sum to 1 (-5 + 4).
   • At index 8, update current_sum to 5 (1 + -5).

3. Update max_sum:

   • At each step, compare current_sum with max_sum and update max_sum accordingly.

4. Result:

   • The maximum subarray sum is 6, and the subarray is [4, -1, 2, 1].