53-maximum-subarray.py

'''Leetcode -https://leetcode.com/problems/maximum-subarray/'''
'''
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
'''

# Solution1
importmath

defmaxSubArray(nums):
max_s=-math.inf
foriinrange(len(nums)):
currentS=0
forjinrange(i, len(nums)):
currentS+=nums[j]
max_s=max(max_s, currentS)
returnmax_s

# T:O(N^2)
# S:O(1)

# Solution2
defmaxSubArray(nums):
max_sum=cur_sum=float('-inf')

foriinnums:
cur_sum=max(cur_sum+i, i)
max_sum=max(max_sum, cur_sum)

returnmax_sum
# T:O(N)
# S:O(1)