Kadanes Algorithm

In this task, I worked on finding the maximum sum of a contiguous subarray in a given array.
This is a classic problem that helps understand optimization over brute-force approaches.

What I Did
I implemented a function maxSubarraySum that returns the largest possible sum from any contiguous subarray.
Example:
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6
👉 The subarray [4, -1, 2, 1] gives the maximum sum = 6

How I Solved It
Brute force checks all subarrays → O(n²) ❌ (bad)
Instead, I used Kadane’s Algorithm → O(n) ✅

Core Idea:
At each step, decide:
Start a new subarray
OR continue the existing one

CODE:

class Solution:
    def maxSubarraySum(self, arr):
        max_sum = arr[0]
        current_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

How It Works
current_sum tracks the best subarray ending at current index
If adding the current element makes it worse → restart
max_sum stores the best result found so far