kadane's Algorithm

Kadane's Algorithm Finding the maximum sum of a contiguous subarray is a classic problem in arrays. A naive solution takes too much time, but Kadane’s Algorithm solves it in the most optimal way. Problem Understanding Given an array, we need to: Find a continuous subarray Such that its sum is maximum Example: Input: [2, 3, -8, 7, -1, 2, 3] Output: 11 ** Optimal Approach: Kadane’s Algorithm ** Instead of checking all subarrays, we use a smart idea: At every element, decide: Start a new subarray OR continue the existing subarray ** Code ** class Solution: def maxSubarraySum(self, arr): max_sum = arr[0] current_sum = arr[0] for i in range(1, len(arr)): current_sum = max(arr[i], current_sum + arr[i]) max_sum = max(max_sum, current_sum) return max_sum ** Step-by-Step Explanation** Step 1: Initialization max_sum = arr[0] current_sum = arr[0] Why? Start from the first element Handles all-negative arrays correctly Complexity: Time: O(1) Space: O(1) Step 2: Traverse Array for i in range(1, len(