Kadanes Algorithm

Introduction Kadane’s Algorithm is an efficient way to find the maximum sum of a contiguous subarray. It is widely used in array and dynamic programming problems. Problem Statement Given an array of integers (both positive and negative), find the contiguous subarray with the maximum sum and return that sum. Approach (Kadane’s Algorithm) We use a dynamic approach: Initialize two variables: current_sum = 0 max_sum = very small number Traverse the array: Add current element to current_sum If current_sum becomes greater than max_sum → update max_sum If current_sum becomes negative → reset it to 0 Python Code python def max_subarray_sum(arr): current_sum = 0 max_sum = float('-inf') for num in arr: current_sum += num max_sum = max(max_sum, current_sum) if current_sum < 0: current_sum = 0 return max_sum # Example arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] print("Maximum Subarray Sum:", max_subarray_sum(arr)) ## Input [-2, 1, -3, 4, -1, 2, 1, -5, 4] ## Output 6