CA 10 - Kadanes Algorithm

The Problem Given an array of integers. The Task is to find the maximum sum of a contiguous subarray. Example: Input: [2, 3, -8, 7, -1, 2, 3] Output: 11 Idea If your current sum becomes negative: Drop it immediately Start fresh from next element Algorithm Logic At each index: current_sum = max(arr[i], current_sum + arr[i]) max_sum = max(max_sum, current_sum) Example Array: [2, 3, -8, 7, -1, 2, 3] Step-by-step: Start with 2 → current = 2 Add 3 → current = 5 Add -8 → current = -3 ❌ (bad → drop) Start fresh at 7 → current = 7 Add -1 → current = 6 Add 2 → current = 8 Add 3 → current = 11 ✅ answer = 11 Python Code class Solution: def maxSubarraySum(self, arr): max_sum = arr[0] current_sum = arr[0] for i in range(1, len(arr)): current_sum = max(arr[i], current_sum + arr[i]) max_sum = max(max_sum, current_sum) return max_sum All numbers are negative: [-2, -4] Answer = -2 (not 0) max_sum = arr[0]