Mastering Kadane's Algorithm

What is Kadane's Algorithm?

Kadane's Algorithm is a powerful technique to find the maximum sum of a contiguous subarray in a one-dimensional array. It runs in O(n) time, making it an optimal solution for problems involving subarray sums.

How It Works

The algorithm uses two variables:

• current_sum: Tracks the sum of the current subarray.
• max_sum: Stores the maximum sum encountered so far.

At each step, it decides:

1. If the current element alone is greater than the sum of the ongoing subarray (current_sum), it starts a new subarray.
2. Otherwise, it continues adding the current element to the ongoing subarray.

Handling Negative Numbers

Kadane's Algorithm efficiently handles arrays with negative numbers by dynamically resetting the current_sum when it falls below zero. This ensures:

• The subarray contributing to max_sum does not include unnecessary negative values.
• The algorithm adapts to the array's state, even when all numbers are negative, by selecting the least negative single element as the maximum sum.

Why Kadane's Algorithm is Optimal

1. Linear Time Complexity: It traverses the array in a single pass.
2. Space Efficiency: Uses constant space, with no additional data structures required.
3. Dynamic Decisions: Ensures the optimal subarray is built without unnecessary calculations.

Pseudo-Code and Implementation

#include <iostream>
#include <vector>
using namespace std;

int kadane(const vector<int>& arr) {
    int max_sum = INT_MIN, current_sum = 0;

    for (int num : arr) {
        current_sum = max(num, current_sum + num);
        max_sum = max(max_sum, current_sum);
    }
    return max_sum;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Maximum Subarray Sum: " << kadane(arr) << endl;
    return 0;
}

Example

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

Key Takeaway

Kadane's Algorithm's ability to dynamically reset the subarray when faced with negatives ensures it always finds the optimal solution. Its simplicity and efficiency make it a cornerstone of competitive programming and algorithmic problem-solving.

Resources

WIP