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 → fastest possible

2. Constant Space
   No extra arrays → 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³) → Too slow

Prefix Sum

Still needs nested loops
Extra space required