53. Maximum Subarray

Medium

Problem:

Find the contiguous subarray that has the maximum sum and return the sum.

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.

https://leetcode.com/problems/maximum-subarray

Solution:

Kadane's Algorithm

At first glance, this might seem like a problem for the two-pointer technique. However, to efficiently solve it using two pointers, sorting is necessary.

Calculate the cumulative sum by continuously adding values from the front. Keep adding the previous values, but discard them if they become 0 or less. By using memoization to accumulate values in sums, and then extracting the maximum value from it, you can find the maximum value of the subarray.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sums: List[int] = [nums[0]]

        for i in range(1, len(nums)):
            sums.append(nums[i] + (sums[i - 1] if sums[i - 1] > 0 else 0))

        print(sums)
        return max(sums)