53. Maximum Subarray

Description

See description at https://leetcode.com/problems/maximum-subarray/

Solutions

Kadane's Algorithm

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

My Solution

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