CA 11 - Kadanes Algorithm - P2

Problem Kadane's Algorithm You are given an integer array arr[]. Your task is to find the maximum sum of a contiguous subarray. A subarray is a continuous part of the array. Input: [2, 3, -8, 7, -1, 2, 3] → Output: 11 Input: [-2, -4] → Output: -2 Input: [5, 4, 1, 7, 8] → Output: 25 Approach We use Kadane’s Algorithm, which efficiently finds the answer in one pass. Keep a running sum of the current subarray At each step, decide whether to continue the current subarray or start fresh Track the maximum sum seen so far Steps: Initialize current_sum and max_sum with the first element Traverse the array: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) This way, we always maintain the best possible subarray sum. Complexity: Time Complexity: O(n) Space Complexity: O(1) def maxSubArray(arr): current_sum = arr[0] max_sum = arr[0] for num in arr[1:]: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum arr = [2, 3, -8, 7, -1, 2