CA 10 - Kadanes Algorithm

Problem Given an integer array arr[], the task is to find the maximum sum of a subarray containing at least one element. A subarray is a continuous part of an array. Output Example 1 Output: 11 Example 2 Output: -2 Example 3 Output: 25 My Approach To solve this problem, I used Kadane’s Algorithm. I keep track of two variables: current_sum to store the sum of the current subarray max_sum to store the maximum sum found so far I iterate through the array: At each element, I decide whether to start a new subarray or continue the existing one I update current_sum as the maximum of the current element or the sum of current element and previous current_sum Then I update max_sum if current_sum is greater This works because it efficiently keeps track of the best possible subarray ending at each position. This approach is efficient because: It requires only one traversal It uses constant extra space Code def max_subarray_sum(arr): current_sum = arr[0] max_sum = arr[0] for num in arr[1:]: current