Core Skill

• Kadane’s Algorithm → efficient dynamic programming technique used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers
• O(n) time → iterating through the array once, keeping track of the maximum sum ending at the current position and the overall maximum sum found so far
• Track best subarray sum

Problems

• Maximum Subarray

Pattern

curr = best = nums[0]
for n in nums[1:]:
    curr = max(n, curr + n)
    best = max(best, curr)

def kadanes_algorithm(arr):
    # Initialize with the first element
    max_so_far = arr[0]
    current_max = arr[0]
    
    # Iterate from the second element
    for i in range(1, len(arr)):
        # Decide to start new or extend existing
        current_max = max(arr[i], current_max + arr[i])
        # Update global max
        max_so_far = max(max_so_far, current_max)
        
    return max_so_far

# Example Usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadanes_algorithm(nums)) # Output: 6