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 1yr ago