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