Kadane’s Algorithm (Maximum Subarray Sum)

🚀 Introduction

Kadane’s Algorithm is used to find the maximum sum of a contiguous subarray within a given array.

👉 It is one of the most important algorithms asked in coding interviews.

❓ Problem Statement

Given an array of integers (positive + negative), find the maximum sum of any contiguous subarray.

Example:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

👉 Subarray: [4, -1, 2, 1] = 6

💡 Intuition

Instead of checking all subarrays (O(n²)), Kadane’s Algorithm works in O(n).

👉 Idea:

If current sum becomes negative → reset it to 0
Keep track of maximum sum

⚙️ Algorithm Steps

Initialize:
- maxSum = -∞
- currentSum = 0
Loop through array:
- Add element to currentSum
- Update maxSum
- If currentSum < 0, reset to 0

🧑‍💻 PHP Implementation

<?php
function kadane($arr) {
    $maxSum = PHP_INT_MIN;
    $currentSum = 0;    foreach ($arr as $num) {
        $currentSum += $num;        if ($currentSum > $maxSum) {
            $maxSum = $currentSum;
        }        if ($currentSum < 0) {
            $currentSum = 0;
        }
    }    return $maxSum;
}// Example
$arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
echo "Maximum Subarray Sum: " . kadane($arr);
?>

<?php
function kadane($arr) {
    $maxSum = PHP_INT_MIN;
    $currentSum = 0;    foreach ($arr as $num) {
        $currentSum += $num;        if ($currentSum > $maxSum) {
            $maxSum = $currentSum;
        }        if ($currentSum < 0) {
            $currentSum = 0;
        }
    }    return $maxSum;
}// Example
$arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
echo "Maximum Subarray Sum: " . kadane($arr);
?>

🔍 Dry Run

Array:

[-2, 1, -3, 4, -1, 2, 1]

Step	Current Sum	Max Sum
-2	-2 → 0	-2
1	1	1
-3	-2 → 0	1
4	4	4
-1	3	4
2	5	5
1	6	6

👉 Final Answer = 6

⚡ Time & Space Complexity

Type	Complexity
Time	O(n)
Space	O(1)

🎯 Why It’s Important

🔥 Very common in interviews
🔥 Base for many DP problems
🔥 Optimized approach (better than brute force)

No comments yet! You be the first to comment.

DSA