Kadanes Algorithm - P2

Problem

You’re given an array of integers and need to find the maximum sum of any contiguous subarray.

---

Strategy

At first, it feels like you need to check every possible subarray.

But that quickly becomes too slow.

Instead, I thought about it differently:
At each position, I asked—

Is it better to continue the current subarray, or start fresh from here?

So for every element:

• Either extend the current sum
• Or start a new subarray from that element

This way, I only pass through the array once.

---

Code

class Solution:
    def maxSubArray(self, arr):
        current_sum = arr[0]
        max_sum = arr[0]

        for i in range(1, len(arr)):
            current_sum = max(arr[i], current_sum + arr[i])
            max_sum = max(max_sum, current_sum)

        return max_sum

---

Key Lines Explained

• current_sum = max(arr[i], current_sum + arr[i])
  This decides whether to:

  • Continue the current subarray
  • Or start a new one

• max_sum = max(max_sum, current_sum)
  
  Keeps track of the maximum sum seen so far.

---

Why This Works

If the current sum becomes negative, it won’t help in building a larger sum later.

So instead of carrying it forward, we reset and start from the current element.

---

Complexity

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

---

Final Note

This problem looks like it needs brute force, but it doesn’t.

Once you focus on making a decision at each step instead of looking at all possibilities, the solution becomes much simpler.