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.