kadane.md

Kadane's Algorithm

• Kadane's Algorithm is an algorithm that can find the maximum sum subarray given an array of numbers in O(n) time and O(1) space

Implementation

• Iterating through the array using an integer variable current, and at each index i, determines if elements before index i are "worth" keeping, or if they should be "discarded".

1. best = negative infinity

2. current = 0

3. for num in nums: 3.1. current = Max(current + num, num) 3.2. best = Max(best, current)

4. return best

Template

def maxSubArray(self, nums: List[int]) -> int:
    # Initialize our variables using the first element.
    current = best = nums[0]
     
    for num in nums[1:]:
        # If current is negative, throw it away. Otherwise, keep adding to it.
        current = max(num, current + num)
        best = max(best, current)
     
    return best

Reference:

• Leetcode Kadane's Algorithm
• Kadane’s Algorithm Explained | HackerNoon

Practice:

• 53. Maximum Subarray
• 152. Maximum Product Subarray
• 918. Maximum Sum Circular Subarray
• 1014. Best Sightseeing Pair