Kadane’s Algorithm – Maximum Subarray Sum

Problem Statement You are given an integer array arr[]. Your task is to find the maximum sum of a contiguous subarray containing at least one element. A subarray is defined as a continuous portion of an array. Examples Example 1: Input: arr = [2, 3, -8, 7, -1, 2, 3] Output: 11 Explanation: The subarray [7, -1, 2, 3] has the largest sum 11. Example 2: Input: arr = [-2, -4] Output: -2 Explanation: The subarray [-2] has the largest sum -2. Example 3: Input: arr = [5, 4, 1, 7, 8] Output: 25 Explanation: The subarray [5, 4, 1, 7, 8] has the largest sum 25. Constraints 1 ≤ arr.size() ≤ 10^5 -10^4 ≤ arr[i] ≤ 10^4 These constraints imply that a brute-force O(n²) solution will not work for large arrays. We need an O(n) solution, which is exactly what Kadane’s Algorithm provides. Approach – Kadane’s Algorithm Kadane’s Algorithm works by keeping track of two variables: current_max – the maximum sum of the subarray ending at the current position. max_so_far – the maximum sum found so far in the ar