Kadanes Algorithm

Problem Statement You are given an integer array arr[]. Your task is to find the maximum sum of a subarray (containing at least one element). Note: A subarray is a continuous part of an array. 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. Even though all elements are negative, we must return the largest among them. Example 3 Input: arr[] = [5, 4, 1, 7, 8] Output: 25 Explanation: Entire array is the maximum subarray. Sum = 5 + 4 + 1 + 7 + 8 = 25 Constraints 1 ≤ arr.size() ≤ 10^5 -10^4 ≤ arr[i] ≤ 10^4 Approach – Kadane’s Algorithm This problem can be solved efficiently using Kadane’s Algorithm. Key Idea At every index, decide: Should we continue the previous subarray? Or start a new subarray from the current element? We keep track of: current_sum → maximum sum ending at current position max_sum → overall maximum f