# 53. Maximum Subarray

See Kadane's Algorithm. This is a slight modification of Kadane's algorithm in that it allows for an input array of all negatives (example: nums = [-5, -3, -7, -2, -4]. The result in this case will be -3. The input array is also assumed to have at least one value.

class Solution:

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

current_sum = nums[0]

high_sum = current_sum

for i in range(1, len(nums)):

current_sum = max(nums[i], current_sum + nums[i])

high_sum = max(current_sum, high_sum)

return high_sum

I was on the right track to the optimal solution which is Kadane's Algorithm. I should have taken extra time to look at my nested if statements. I knew it was bad, but just submitted anyway. If I stopped and looked closer, I think I could have simplified it closer to Kadane's Algorithm. I was happy I found the O(N) solution.

class Solution:

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

current_sum = nums[0]

high_sum = current_sum

for i in range(1, len(nums)):

if current_sum < 0:

if nums[i] > 0:

current_sum = nums[i]

else:

current_sum = max(current_sum, nums[i])

else:

current_sum += nums[i]

high_sum = max(current_sum, high_sum)

return high_sum

Last modified 2yr ago