53. Maximum Subarray - Leetcode Python Solution

 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.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Here's a breakdown of the solution:

Initialize two variables, sum and maxsum, to keep track of the current sum of subarrays and the maximum sum found so far. Set sum to 0 and maxsum to the first element of the nums array (nums[0]).

Iterate through the elements in the nums array one by one, using a for loop. For each element, perform the following steps:

Check if the current sum is negative (sum < 0). If it is, reset sum to 0. This is because if the previous subarray had a negative sum, it's better to start with the current element as a new potential subarray.

Add the current element (num) to the sum. This is done to extend the current subarray and keep track of its sum.

Compare the current sum with the maxsum. If the current sum is greater than maxsum, update maxsum to be equal to sum. This is how you keep track of the maximum subarray sum found so far.

After the loop has iterated through all elements in the nums array, return the maxsum, which will be the maximum sum of a subarray.

The algorithm effectively maintains a running sum of subarrays and keeps track of the maximum sum found so far. By resetting the sum to 0 whenever it becomes negative, it ensures that it only considers contiguous subarrays with positive contributions. This algorithm has a time complexity of O(n), where n is the number of elements in the nums array.

In [ ]:

from typing import List
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum=0
        maxsum=nums[0]
        for num in nums:
            if sum<0:
                sum=0
            sum = sum + num
            if sum>maxsum:
                maxsum = sum
        return maxsum
s = Solution()
s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])

Out[ ]:

6