Kadane’s Algorithm: Finding the Maximum Subarray Sum

Introduction In many problems involving arrays, we are interested in finding a subarray that gives the maximum possible sum. A subarray is a continuous part of an array. Kadane’s Algorithm is an efficient way to solve this problem in linear time. Problem Statement Given an integer array arr[], find the maximum sum of a contiguous subarray. Example 1 Input: arr = [2, 3, -8, 7, -1, 2, 3] Output: 11 Explanation: The subarray [7, -1, 2, 3] has the maximum sum of 11. Example 2 Input: arr = [-2, -4] Output: -2 Explanation: The largest element itself is the answer since all values are negative. Kadane’s Algorithm (Efficient Approach) Traverse the array once Keep track of: Current sum Maximum sum so far At each step: Add the current element to the running sum If the sum becomes negative, reset it to zero Update the maximum sum if needed Python Implementation def max_subarray_sum(arr): max_sum = arr[0] current_sum = 0 for num in arr: current_sum += num if current_sum > max_sum: max_sum = cur