Kadane’s Algorithm – Maximum Subarray Sum

Problem Statement: Given an integer array, find the maximum sum of a contiguous subarray. Example: Input: [2, 3, -8, 7, -1, 2, 3] Output: 11 Approach (Kadane’s Algorithm): We iterate through the array while keeping track of: Current subarray sum Maximum sum found so far At each step, we decide whether to continue the current subarray or start a new one. Code: def max_subarray_sum(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 Explanation: current_sum stores the maximum sum ending at current position If adding the current element reduces the sum, we start fresh max_sum keeps track of the overall maximum Time Complexity: O(n), single pass through array Space Complexity: O(1), constant space