Kadane’s Algorithm(p2)

Hi everyone!
While practicing array problems, I came across this famous problem of finding the maximum sum of a subarray. Initially, it looked tricky, but Kadane’s Algorithm made it simple.

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
First, I thought of checking all subarrays, but that would take O(n²) time.

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

Logic
Keep adding elements to a running sum
If the sum becomes negative - reset it to 0
Track the maximum sum seen so far

Code (Python)

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

This algorithm also works when all elements are negative because we initialize max_sum with the first element.

What I Learned
Brute force is not always efficient
Kadane’s Algorithm is a must-know for arrays
Resetting sum is the key idea

Thanks for reading!
Feel free to share your thoughts or improvements.