Maximum Subarray Sum (Kadane’s Algorithm)

In this task, I worked on finding the maximum sum of a contiguous subarray within a given array. This problem is important because it teaches how to optimize brute-force solutions using dynamic programming concepts.
What I Did

I created a function maxSubarraySum that takes an array as input and returns the maximum possible sum of any contiguous subarray.

Example:
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6
How I Solved It

A brute-force approach would check all subarrays → O(n²) (too slow).

Instead, I used Kadane’s Algorithm, which works in one pass.
Step-by-step approach:

• I initialized: max_sum = first element current_sum = first element
• Then I looped through the array starting from index 1
• For each element: Decide whether to: Start a new subarray (arr[i]) OR extend the existing subarray (current_sum + arr[i])
• Update current_sum using: current_sum = max(arr[i], current_sum + arr[i])
• Update max_sum if current sum is greater CODE: ''' python

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
The algorithm keeps track of two things:
current_sum: Best sum ending at current index
max_sum: Best sum found so far
At every step:
If adding the current element makes things worse → restart
Otherwise → keep extending
This avoids checking all subarrays.