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 >