Maximum Subarray

Intuition

• Through Kadanes Algorithm, you are checking in which case you should extend the current subarray, or just start a new subarray.
• The idea is:
  • Make the greedy choice in each iteration.
    • Get the maximum between the current number or the current number plus the greedy maximum of before.
  • Then store the global maximum.
    • You need the global maximum since:
      • There is no guarantee that the locally maximum subarray sum you have found will not become larger as you move on to the next subarrays.
      • Likewise, there is no guarantee that the new subarray you have moved on to will have a larger globally optimal maximum subarray sum.
        • ex) [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i	nums[i]	Calculation of local_max	Calculation of res	local_max	res
1	1	max(1, -2 + 1) = 1	max(-2, 1) = 1	1	1
2	-3	max(-3, 1 - 3) = -2	max(1, -2) = 1	-2	1
3	4	max(4, -2 + 4) = 4	max(1, 4) = 4	4	4
4	-1	max(-1, 4 - 1) = 3	max(4, 3) = 4	3	4
5	2	max(2, 3 + 2) = 5	max(4, 5) = 5	5	5
6	1	max(1, 5 + 1) = 6	max(5, 6) = 6	6	6
7	-5	max(-5, 6 - 5) = 1	max(6, 1) = 6	1	6
8	4	max(4, 1 + 4) = 5	max(6, 5) = 6	5	6

Complexity

Runtime

$O(N)$ simple for loop

Space

$O(1)$ no axillary space

Code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        global_max = nums[0]
        local_max = nums[0]
        for i in range(1, len(nums)):
            if nums[i] + local_max >= nums[i]:
                local_max += nums[i]
            else: # reset
                local_max = nums[i]
            global_max = max(global_max, local_max)
            
        return global_max

Cards

START Basic Front: Maximum Subarray Back: Store the current element or the previous maximum’s $\times$ the current element.

END

---

References

• Maximum Subarray
• ChatGPT Local Maximum vs. Global Maximum
• Kadane’s algorithm intuition explained | Claude