KADANE'S ALGORITHM

When I first saw this problem, it looked tricky because it asks for the maximum sum of a subarray. But after working through it, I realized the solution is simple if you focus on one idea: keep track of the current sum and the maximum sum so far. Problem We are given an array of integers. The task is to find the maximum sum of a contiguous subarray. Examples: Python arr = [2, 3, -8, 7, -1, 2, 3] Output: 11, because [7, -1, 2, 3] has the largest sum Python arr = [-2, -4] Output: -2, because [-2] is the largest sum subarray Python arr = [5, 4, 1, 7, 8] Output: 25, because [5, 4, 1, 7, 8] is the whole array What I Noticed Instead of checking all subarrays (which would take O(n²) or O(n³) time), I focused on: Tracking the current sum of a subarray Updating the maximum sum found so far Resetting the current sum when it becomes negative This idea is the heart of Kadane’s Algorithm. What Helped Me Using two variables made everything easy: max_so_far → stores the maximum sum found so far curre