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
current_sum → stores the sum of the current subarray
At each step:
Add the current element to current_sum
Update max_so_far if current_sum is bigger
If current_sum becomes negative, reset it to 0
This ensures we always keep the best sum and ignore parts that reduce the sum.

Code (Python)
Python
class Solution:
def maxSubArray(self, arr):
max_so_far = arr[0] # Initialize with first element
current_sum = arr[0] # Current subarray sum

    for i in range(1, len(arr)):
        # Either start new subarray at arr[i] or extend current
        current_sum = max(arr[i], current_sum + arr[i])
        # Update the maximum sum found so far
        max_so_far = max(max_so_far, current_sum)

    return max_so_far

** Example Usage**
Python
arr = [2, 3, -8, 7, -1, 2, 3]
solution = Solution()
print(solution.maxSubArray(arr))
Output:
Plain text
11
⏱️ Complexity
Time: O(n) — iterate through the array once
Space: O(1) — only two variables needed

What I Learned
This problem is less about complex code and more about thinking clearly:
Track the current sum and maximum sum
Reset when the current sum goes negative
Step by step, you can solve it efficiently
Kadane’s Algorithm is a classic example of a greedy approach.

Final Thought
At first, finding the maximum subarray sum seemed hard.
But once I broke it down:
** “Add, compare, reset if negative.”**
…it became intuitive.
This problem shows that simple logic often beats brute force.