Leet Code
brian | Published: Jan. 19, 2025, 2:08 p.m. | Updated: July 9, 2025, 9:25 p.m.
'''
53. Maximum Subarray
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.
'''
class Solution:
def maxSubArray(self, nums:list):
#check if there is only one value, then just return it
#as that would be the max
if len(nums) == 1:
return nums[0]
#initialize the vals as 0
maxSum = 0
currMax = 0
for x in range(len(nums)):
#add the currMax to the current value in the list
currMax+= nums[x]
#if the currMax is less than 0 then reset back to 0
if currMax < 0:
currMax = 0
#get the max by comparing both the maxSum and the currentMax
maxSum = max(maxSum,currMax)
#return the max contigeous val
return maxSum
if __name__ == '__main__':
nums = [-2,1,-3,4,-1,2,1,-5,4] #should return 6
obj1 = Solution()
print(obj1.maxSubArray(nums))