kadane's Algorithm

Kadane's Algorithm

Finding the maximum sum of a contiguous subarray is a classic problem in arrays. A naive solution takes too much time, but Kadane’s Algorithm solves it in the most optimal way.

Problem Understanding

Given an array, we need to:

Find a continuous subarray
Such that its sum is maximum

Example:

Input: [2, 3, -8, 7, -1, 2, 3]
Output: 11
** Optimal Approach: Kadane’s Algorithm
**
Instead of checking all subarrays, we use a smart idea:

At every element, decide:

Start a new subarray
OR continue the existing subarray
** 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

** Step-by-Step Explanation**
Step 1: Initialization
max_sum = arr[0]
current_sum = arr[0]
Why?

Start from the first element
Handles all-negative arrays correctly
Complexity:
Time: O(1)
Space: O(1)

Step 2: Traverse Array
for i in range(1, len(arr)):
Why?

We process each element once
Complexity:
Time: O(n)

Step 3: Core Logic
current_sum = max(arr[i], current_sum + arr[i])
Why?

At each step, we decide:

Start fresh (arr[i])
OR continue (current_sum + arr[i])
This is the heart of Kadane’s Algorithm

Step 4: Update Maximum
max_sum = max(max_sum, current_sum)
Why?
Keep track of the best sum found so far

Why This Approach Is Best

1. Single Pass
   Only one loop that fastest possible

2. Constant Space
   No extra arrays means memory efficient

3. Handles All Cases
   Works even if all numbers are negative

Why Other Approaches Fail
Brute Force

Check all subarrays
Time: O(n² / n³) is Too slow

Prefix Sum

Still needs nested loops
Extra space required