S Square

Kadane’s Algorithm is a dynamic programming approach used to find the maximum sum of a contiguous subarray in linear time O(n). It works by iterating through the array while keeping track of the maximum subarray sum ending at the current index (max_ending_here) and the overall maximum so far (max_so_far). At each step, it decides whether to extend the current subarray or start a new one, based on which yields a higher sum. This efficient method handles negative numbers and avoids checking all possible subarrays.