Kadane’s Algorithm: Maximum Subarray Sum Problem

Introduction to Kadane’s Algorithm

Kadane’s algorithm is an elegant and efficient solution to the classic maximum subarray sum problem. The core idea is to find the contiguous subarray (a subsequence where elements occupy consecutive positions) within a given array that boasts the largest sum.

The Essence of Kadane’s Algorithm

At its core, Kadane’s algorithm follows a clever principle:

1. Track the Current Sum: It maintains a variable runningSum to keep track of the sum of the subarray being examined so far.
2. Maximizing Potential: As the algorithm iterates through the array, it adds each element to runningSum. The goal is to accumulate as much sum as possible.
3. Discard Negatives: Crucially, whenever runningSum dips below zero, it gets reset to zero. This signifies that the current subarray is no longer contributing positively and it’s better to start fresh from the next element.
4. Keeping the Best: Throughout the process, another variable maxSum stores the maximum sum encountered. Every time runningSum exceeds the current maxSum, it means we’ve discovered a new contender for the richest subarray.

Let’s crunch some numbers with examples:

Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6

Explanation: The subarray [4, -1, 2, 1] gives us the largest sum, which is 6.

Kadane’s Algorithm: Code Implementations

Let’s see how Kadane’s Algorithm translates into code in various programming languages (Java, JavaScript, C++, Python):

Java:

public class Kadane {

    public static int kadane(int[] array) {
        int runningTotal = 0;
        int championScore = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            runningTotal = Math.max(runningTotal + array[i], array[i]);
            championScore = Math.max(championScore, runningTotal);
        }
        return championScore;
    }

    public static void main(String[] args) {
        int[] array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(kadane(array)); // Output: 6
    }
}

JavaScript:

function kadane(arr) {
    let maxEndingHere = 0;
    let maxSoFar = Number.MIN_SAFE_INTEGER;

    for (let num of arr) {
        maxEndingHere = Math.max(num, maxEndingHere + num);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

// Example usage:
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("Maximum subarray sum:", kadane(arr)); // Output: 6

C/C++:

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

int kadane(int arr[], int n) {
    int maxEndingHere = 0;
    int maxSoFar = INT_MIN;

    for (int i = 0; i < n; ++i) {
        maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum subarray sum: " << kadane(arr, n) << endl; // Output: 6
    return 0;
}

Python:

def kadane(arr):
    maxEndingHere = maxSoFar = float('-inf')

    for num in arr:
        maxEndingHere = max(num, maxEndingHere + num)
        maxSoFar = max(maxSoFar, maxEndingHere)

    return maxSoFar

# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum subarray sum:", kadane(arr))  # Output: 6

Let’s Break it Down

• All implementations initialize maxSum to a very low value and runningSum to zero.
• The core logic within the loop is the same:
  • runningSum = Math.max(num, runningSum + num) ensures a fresh start when the current subarray sum becomes negative.
  • maxSum = Math.max(maxSum, runningSum) updates the maximum sum when a richer subarray is found.

Here’s a breakdown of the calculation steps:

Technical Expertise for Explorers:

• Time Complexity: O(n), signifying the algorithm executes efficiently, taking a time proportional to the array size (n). This makes it ideal for navigating vast code caverns.
• Space Complexity: O(1), signifying the algorithm uses constant additional space regardless of the input size. It travels light, making it valuable for resource-constrained environments.

Conclusion

Congratulations! You’ve conquered the basics of Kadane’s algorithm. Remember, it’s like a smart bucket trick that helps you find the group of numbers with the highest combined sum, even if it’s negative. Whether you’re dealing with friends’ debts or analyzing stock prices, Kadane’s algorithm offers a powerful and straightforward method to unearth the “richest bunch” within your data.

So, the next time you encounter a list of numbers, remember this simple yet effective tool. With a bit of practice, you’ll be a master at identifying the subarray with the most “cash,” positive or negative, empowering you to unlock valuable insights from your data!

I hope this article has been helpful. Please feel free to leave a comment below if you have any questions or contact us. If you want to solve the problem, visit leetcode.