What is Kadane’s Algorithm and how does it work for finding the maximum subarray sum?

Could someone provide a step-by-step explanation (and maybe a simple code example in C++) to illustrate how it is applied?

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.