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.