Kadane’s Algorithm

Hi everyone!
Today I learned one of the most famous algorithms in arrays — Kadane’s Algorithm. It helps us find the maximum sum of a subarray in an efficient way.

Problem
Given an array, find the maximum sum of a contiguous subarray.

Example:
Input: [2, 3, -8, 7, -1, 2, 3]

Output: 11

My Approach
At first, I thought of checking all subarrays, but that would take a lot of time (O(n²)).

Then I learned Kadane’s Algorithm which solves it in O(n).

Logic

• Keep adding elements to current sum
• If the sum becomes negative → reset it to 0
• Keep track of maximum sum seen so far

Code (Python)
class Solution:
class Solution:
def maxSubarraySum(self, arr):
max_sum = arr[0]
curr_sum = 0

    for num in arr:
        curr_sum += num
        if curr_sum > max_sum:
            max_sum = curr_sum

        if curr_sum < 0:
            curr_sum = 0

    return max_sum

Time & Space Complexity

• Time: O(n)
• Space: O(1)

Important Point
Even if all numbers are negative, this algorithm still works because we initialize max_sum with the first element.

What I Learned

• Dynamic programming can optimize brute force solutions
• Kadane’s Algorithm is very useful for subarray problems
• Resetting sum is the key idea

Thanks for reading!
If you found this helpful, feel free to share your thoughts.