Maximum Subarray Sum (Kadane's Algorithm): Explanation & Solution

Last update on May 15 2024 13:16:48 (UTC/GMT +8 hours)

Problem Statement

Maximum Subarray Sum (Kadane's Algorithm):

Find the contiguous subarray with the largest sum.

Introduction to the Problem
Underlying Concepts
Examples and Illustrations
Brute Force Approach
Kadane's Algorithm
Algorithmic Thinking
Common Mistakes and Pitfalls
Coding Best Practices
Testing and Debugging
Algorithm Analysis
Application in Real-world Projects
Solution for different languages
Time and Space Complexity

Introduction to the Problem

Problem Statement:

The "Maximum Subarray Sum problem" entails finding the contiguous subarray within a given array of integers that has the largest sum.
Input:

The input to the Max Subarray Sum problem is an array of integers. This array represents the sequence of numbers from which we need to find the contiguous subarray with the largest sum.
For example, given an input array [−2, 1, −3, 4, −1, 2, 1, −5, 4], our task is to identify the contiguous subarray within this array that yields the maximum sum.

Output:

The output of the problem is the sum of the maximum subarray found within the given array.
In the example array [−2, 1, −3, 4, −1, 2, 1, −5, 4], the maximum subarray sum is 6, which corresponds to the subarray [4, −1, 2, 1].
Hence, the output would be 6.

Real-world Scenario:

In stock price analysis, finding the maximum subarray sum can help identify the most profitable period for buying and selling stocks.
For instance, given historical stock prices, determining the maximum subarray sum would reveal the best time to buy and sell stocks for maximum profit.

Data Structure: DSA Maximum Subarray Sum Kadane Algorithm

Underlying Concepts:

Contiguous Subarray:

A contiguous 'subarray', also known as a contiguous segment or subsequence, refers to a sequence of elements within an array that are adjacent to each other.
Unlike non-contiguous 'subarrays', where elements are not required to be adjacent, contiguous ‘subarrays’ must maintain the order of elements as they appear in the original array.
For example, in the array [1, 2, -3, 4, 5], the contiguous 'subarray' [2, -3, 4] represents a contiguous segment of the array.

Prefix Sum:

The prefix sum of an array is a technique used to preprocess the array in order to efficiently compute the sum of any contiguous 'subarray'.
It involves calculating the cumulative sum of elements from the beginning of the array up to each index.
The prefix sum array, also known as the cumulative sum array, allows for constant-time computation of 'subarray' sums by subtracting prefix sums at the starting and ending indices of the 'subarray'.
For example, given the array [1, -2, 3, 5, -3, 2], its prefix sum array would be [1, -1, 2, 7, 4, 6], where prefix_sum[i] represents the sum of elements from index 0 to i in the original array.

Examples and Illustrations:

Walkthrough examples:

Walkthrough examples involve step-by-step demonstrations of how to identify the maximum ‘subarray’ sum in a given array using "Kadane's Algorithm".
For instance, consider the array [−2, 1, −3, 4, −1, 2, 1, −5, 4]. Walk through the algorithm's execution to find the maximum ‘subarray’ sum and the corresponding ‘subarray’.

Example:

Given array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Initialize 'max_sum' and 'current_sum' to the first element: max_sum = current_sum = -2
Iterate through the array from the second element:
- For each element, update 'current_sum':
- If adding the current element to 'current_sum' increases it, update 'current_sum'.
- If 'current_sum' becomes negative, reset it to the current element.
- Update 'max_sum' if 'current_sum' is greater than 'max_sum'.

After the iteration, ’max_sum’ represents the maximum 'subarray' sum.

Brute Force Approach:

Naive Solution:

The naive solution to the “Max Subarray Sum” problem involves exploring all possible 'subarrays' within the given array. It also determines the sum of each 'subarray'.
This approach typically utilizes nested loops to generate all possible ‘subarrays’, compute their sums, and track the maximum sum found so far.
By exhaustively checking every 'subarray', the algorithm identifies the 'subarray' with the maximum sum.

Example:

Given array: [−2, 1, −3, 4, −1, 2, 1, −5, 4]

Naive Solution:

- Iterate through all possible subarrays:
- Subarray [−2] → Sum = -2
- Subarray [−2, 1] → Sum = -1
- Subarray [−2, 1, −3] → Sum = -4
- ...
- Subarray [4, −1, 2, 1, −5, 4] → Sum = 5
- Identify the subarray with the maximum sum: [4, −1, 2, 1]

Complexity Analysis:

Time Complexity:

The brute force approach examines all possible ‘subarrays’, leading to a time complexity of O(n^3), where n is the size of the input array.
This is because there are O(n^2) ‘subarrays’, and computing the sum of each ‘subarray’ requires O(n) time.

Space Complexity:

The space complexity of the brute force approach is O(1) since it does not require additional space proportional to the input size.

Limitations:

"Brute Force Approach" becomes impractical for large input arrays due to its cubic time complexity.
It is inefficient for solving the “Max Subarray Sum” problem when more efficient algorithms, like "Kadane's Algorithm", exist.

Kadane's Algorithm:

Introduction:

“Kadane's Algorithm” is a dynamic programming-based approach devised to efficiently find the maximum ‘subarray’ sum within an array of integers.
It is widely acclaimed for its simplicity and effectiveness in solving the Max Subarray Sum problem.

Algorithmic Steps:

Initialization:

Start by initializing two variables: 'max_sum' and 'current_sum'.
Set both 'max_sum' and 'current_sum' to the value of the first element in the array.

Iteration:

Iterate through the array, starting from the second element.
For each element, update 'current_sum' as follows:

If adding the current element to 'current_sum' increases its value, update 'current_sum'.
If 'current_sum' becomes negative, reset it to the value of the current element.

Update 'max_sum' if 'current_sum' is greater than 'max_sum'.

Final Result:

After completing the iteration, 'max_sum' represents the maximum subarray sum within the given array.

Visualization:

Data Structure: DSA Maximum Subarray Sum Kadane Algorithm evaluation

Algorithmic Thinking:

Dynamic Programming:

"Kadane's Algorithm" utilizes dynamic programming principles to efficiently solve the Max Subarray Sum problem.
It employs a bottom-up approach, iteratively updating a solution to a smaller subproblem to compute the solution to the larger problem.
Specifically, "Kadane's Algorithm" maintains two variables: 'current_sum' and 'max_sum'. It iterates through the array, updating 'current_sum' based on the current element and the maximum sum encountered so far.
By iteratively updating 'current_sum', "Kadane's Algorithm" effectively identifies the maximum ‘subarray’ sum without revisiting previously solved subproblems, thus demonstrating the essence of dynamic programming.

Optimality:

"Kadane's Algorithm" guarantees the optimal solution for the “Max Subarray Sum problem”.
The algorithm's optimality stems from its ability to consider all possible subarrays and select the one with the maximum sum.
By maintaining two variables ('current_sum' and 'max_sum') and efficiently updating them as it traverses the array, "Kadane's Algorithm" ensures that the chosen subarray yields the maximum sum possible.
Moreover, "Kadane's Algorithm" has a time complexity of O(n), making it highly efficient for solving the problem, further solidifying its status as an optimal solution.

Common Mistakes and Pitfalls:

Empty Array:

Addressing the Edge Case:

One common mistake is overlooking the edge case of an empty array.
When the input array is empty, "Kadane's Algorithm" may produce incorrect results if not handled properly.

Handling the Empty Array Case:

To address this edge case, it's essential to include a check at the beginning of the algorithm to handle empty arrays.
If the array is empty, the algorithm should return a default value or indicate that the maximum subarray sum is zero.

Handling Negative Numbers:

Potential Issues:

Another common pitfall is not considering the impact of negative numbers in the input array.
Negative numbers can pose challenges as they may decrease the cumulative sum, potentially leading to incorrect results if not handled appropriately.

Handling Negative Numbers:

"Kadane's Algorithm" is designed to handle negative numbers effectively.
It accounts for negative numbers by resetting the 'current_sum' to the current element if 'current_sum' becomes negative.
By resetting 'current_sum', the algorithm ensures that it always considers the maximum sum contiguous subarray, even if negative numbers are present in the array.

Coding Best Practices:

Readable Code:

Emphasizing Clarity:

It's crucial to emphasize the importance of writing clean and understandable code, especially when implementing "Kadane's Algorithm".
Clear and readable code enhances maintainability and reduces the likelihood of errors.

Commenting and documentation:

Encourage the use of comments and documentation to explain the purpose of variables, functions, and critical sections of code.
Comments provide insights into the algorithm's logic, making it easier for others (and your future self) to understand the code.

Variable Naming:

Significance of Meaningful Names:

Discuss the significance of choosing meaningful variable names for clarity and understanding.
Variable names should accurately reflect the data they store or the role they play in the algorithm.
Meaningful names enhance code readability and comprehension, facilitating easier debugging and maintenance.

Examples:

Instead of using generic names like 'x' or 'temp', opt for descriptive names such as 'current_sum' or 'max_sum'.
Choose variable names that convey their purpose within the algorithm, such as 'current_element' or 'array_length'.

Testing and Debugging:

Test cases:

Providing Comprehensive Test Cases:

Offer a set of test cases to thoroughly verify the correctness of the "Kadane's Algorithm" implementation.
Test cases should cover various scenarios, including arrays with positive and negative numbers, arrays containing only negative numbers, arrays with a single element, and edge cases such as empty arrays.
Each test case should have an expected output against which the algorithm's output can be compared for validation.

Example Test Cases:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4].
Expected Output: 6 (subarray [4, -1, 2, 1]).
Input: [1, 2, 3, 4, 5].
Expected Output: 15 (entire array).
Input: [-2, -3, -1, -5].
Expected Output: -1 (single element -1).
Input: [] (empty array).
Expected Output: 0.

Debugging Techniques:

Using Print Statements:

One common debugging strategy is to insert print statements at various points in the code to inspect the values of variables and the execution flow.
Printing intermediate results helps identify incorrect values or unexpected behavior.

Using a Debugger:

Utilize debugging tools provided by IDEs or programming languages to step through the code and observe its execution in real-time.
Debuggers allow for precise inspection of variables, control flow, and function calls, aiding in identifying and fixing errors.

Code Review:

Conduct code reviews with peers or mentors to gain insights from fresh perspectives.
Peer reviews help identify logical errors, inefficiencies, or areas for improvement in the codebase.

Error Handling:

Implement robust error handling mechanisms to gracefully handle unexpected inputs or edge cases.
Proper error handling prevents the algorithm from crashing and provides meaningful feedback to users in case of errors.

Algorithm Analysis:

Time and Space Complexity:

Time Complexity:

"Kadane's Algorithm" has a time complexity of O(n), where n is the size of the input array.
The algorithm iterates through the array once, processing each element in constant time.
As a result, the time complexity is linear and directly proportional to the size of the input array.

Space Complexity:

"Kadane's Algorithm" has a space complexity of O(1), meaning it requires constant space irrespective of the size of the input array.
The algorithm only maintains a constant number of variables ('max_sum', 'current_sum', etc.), regardless of the input size.
It does not rely on additional data structures or recursive calls, resulting in minimal memory usage.

Comparative Analysis:

Performance Comparison:

Comparing "Kadane's Algorithm" with the brute force approach highlights the significant performance improvement achieved by "Kadane's Algorithm".
The brute force approach has a time complexity of O(n^2), where n is the size of the input array, due to its nested loop structure.
In contrast, "Kadane's Algorithm's" linear time complexity of O(n) makes it significantly more efficient, especially for large input arrays.

Space Complexity Comparison:

Both "Kadane's Algorithm" and the “Brute force approach” have a space complexity of O(1), indicating minimal memory usage.
However, "Kadane's Algorithm's" superior time complexity makes it a more favorable choice in terms of both time and space efficiency.

Overall Efficiency:

"Kadane's Algorithm's" superior time complexity and comparable space complexity make it the preferred choice for solving the “Max Subarray Sum problem".

Application in Real-world Projects:

Data Analysis:

Financial Analysis:

In financial analysis, finding the maximum 'subarray' sum is crucial for identifying profitable trading strategies.
Traders and investors use the maximum 'subarray' sum to analyze stock price movements over time and determine optimal buying and selling points.
By identifying periods of consistent gains or losses, traders can make informed decisions to maximize profits and minimize risks.

Image Processing:

In image processing, the maximum 'subarray' sum can be used for feature extraction and pattern recognition.
For instance, in object detection, the maximum ‘subarray’ sum can help identify regions of interest within an image that contain significant features or anomalies.

Further Exploration:

Finding the Subarray Itself:

While "Kadane's Algorithm" efficiently computes the maximum 'subarray' sum, learners can explore additional challenges related to finding the 'subarray' itself.
This includes identifying the starting and ending indices of the maximum 'subarray' or returning the actual elements comprising the 'subarray'.
Learners can experiment with modifying "Kadane's Algorithm" or combining it with other techniques to address these variations of the problem.

Solution for different languages:

Python - Max Subarray Sum problem

Code:

def max_subarray_sum(nums):
    if not nums:  # Check if the array is empty
        return 0
    
    max_sum = current_sum = nums[0]  # Initialize max_sum and current_sum with first element
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)  # Update current_sum
        max_sum = max(max_sum, current_sum)  # Update max_sum
    return max_sum

# Test Cases
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # Output: 6
print(max_subarray_sum([-2, -3, 4, -1, -2, 1, 5, -3]))   # Output: 7
print(max_subarray_sum([1, 2, 3, 4, 5]))                 # Output: 15
print(max_subarray_sum([-1]))                            # Output: -1
print(max_subarray_sum([]))                              # Output: 0

Output:

Explanation of the said Python code:

The function "max_subarray_sum(nums)" takes an array 'nums' as input and returns the maximum subarray sum.
It first checks if the input array 'nums' is empty. If it is, it returns 0, indicating that the maximum subarray sum in an empty array is 0.
It initializes two variables 'max_sum' and 'current_sum' with the value of the first element of the array 'nums'. These variables represent the maximum sum found so far and the sum of the current subarray being considered, respectively.
Then, it iterates through the array 'nums' starting from the second element (nums[1:]).
For each element 'num' in the array, it updates 'current_sum' using the maximum of the current element alone ('num') or the sum of the current element and the previous 'current_sum'.
It also updates 'max_sum' to store the maximum of the previous 'max_sum' and the updated 'current_sum'.
After iterating through all elements of the array, it returns the final 'max_sum', which represents the maximum subarray sum.
Finally, it includes some test cases to demonstrate the function's correctness and output the results.

Java - Max Subarray Sum problem

Code:

public class MaxSubarraySum {
    public static int maxSubarraySum(int[] nums) {
        if (nums.length == 0) {  // Check if the array is empty
            return 0;
        }
        
        int maxSum = nums[0];  // Initialize maxSum and currentSum with first element
        int currentSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);  // Update currentSum
            maxSum = Math.max(maxSum, currentSum);  // Update maxSum
        }
        return maxSum;
    }

    public static void main(String[] args) {
        // Test Cases
        System.out.println(maxSubarraySum(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));  // Output: 6
        System.out.println(maxSubarraySum(new int[]{-2, -3, 4, -1, -2, 1, 5, -3}));   // Output: 7
        System.out.println(maxSubarraySum(new int[]{1, 2, 3, 4, 5}));                 // Output: 15
        System.out.println(maxSubarraySum(new int[]{-1}));                            // Output: -1
        System.out.println(maxSubarraySum(new int[]{}));                              // Output: 0
    }
}

Output:

Explanation of the said Java code:

The class 'MaxSubarraySum' contains a static method "maxSubarraySum()" that takes an array 'nums' as input and returns the maximum subarray sum.
Inside the "maxSubarraySum()" method, it first checks if the input array 'nums' is empty. If it is, it returns 0, indicating that the maximum subarray sum in an empty array is 0.
It initializes two variables 'maxSum' and 'currentSum' with the value of the first element of the array 'nums'. These variables represent the maximum sum found so far and the sum of the current subarray being considered, respectively.
Then, it iterates through the array 'nums' starting from the second element.
For each element 'num' in the array, it updates 'currentSum' using the maximum of the current element alone (nums[i]) or the sum of the current element and the previous 'currentSum'.
It also updates 'maxSum' to store the maximum of the previous 'maxSum' and the updated 'currentSum'.
After iterating through all elements of the array, it returns the final 'maxSum', which represents the maximum subarray sum.
The "main()" method contains test cases to demonstrate the correctness of the "maxSubarraySum()" method.

C++ - Max Subarray Sum problem

Code:

#include <iostream>
#include <vector>

using namespace std;

int maxSubarraySum(const vector<int>& nums) {
    if (nums.empty()) {  // Check if the array is empty
        return 0;
    }
    
    int maxSum = nums[0];  // Initialize maxSum and currentSum with first element
    int currentSum = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);  // Update currentSum
        maxSum = max(maxSum, currentSum);  // Update maxSum
    }
    return maxSum;
}

int main() {
    // Test Cases
    cout << maxSubarraySum({-2, 1, -3, 4, -1, 2, 1, -5, 4}) << endl;  // Output: 6
    cout << maxSubarraySum({-2, -3, 4, -1, -2, 1, 5, -3}) << endl;   // Output: 7
    cout << maxSubarraySum({1, 2, 3, 4, 5}) << endl;                 // Output: 15
    cout << maxSubarraySum({-1}) << endl;                            // Output: -1
    cout << maxSubarraySum({}) << endl;                              // Output: 0
    return 0;
}

Output:

Explanation of the said C++ code:

maxSubarraySum function:

Parameters: The function takes a constant reference to a vector of integers ('nums').
Returns: It returns an integer, which represents the maximum sum of a contiguous subarray.
Algorithm: It initializes two variables, 'maxSum' and 'currentSum', with the first element of the input array 'nums'. Then, it iterates through the array starting from the second element. At each iteration, it updates 'currentSum' by choosing the maximum between the current element and the sum of the current element and the previous 'currentSum'. Simultaneously, it updates 'maxSum' by choosing the maximum between the current 'maxSum' and 'currentSum'. Finally, it returns 'maxSum'.

C# - Max Subarray Sum problem

Code:

using System;

public class MaxSubarraySum
{
    public static int MaxSubArraySum(int[] nums)
    {
        if (nums.Length == 0)
        {  // Check if the array is empty
            return 0;
        }

        int maxSum = nums[0];  // Initialize maxSum and currentSum with first element
        int currentSum = nums[0];
        for (int i = 1; i < nums.Length; i++)
        {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);  // Update currentSum
            maxSum = Math.Max(maxSum, currentSum);  // Update maxSum
        }
        return maxSum;
    }

    public static void Main(string[] args)
    {
        // Test Cases
        Console.WriteLine(MaxSubArraySum(new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }));  // Output: 6
        Console.WriteLine(MaxSubArraySum(new int[] { -2, -3, 4, -1, -2, 1, 5, -3 }));   // Output: 7
        Console.WriteLine(MaxSubArraySum(new int[] { 1, 2, 3, 4, 5 }));                 // Output: 15
        Console.WriteLine(MaxSubArraySum(new int[] { -1 }));                            // Output: -1
        Console.WriteLine(MaxSubArraySum(new int[] { }));                              // Output: 0
    }
}

Output:

Explanation of the said C# code:

Class Definition:

The code defines a public class named "MaxSubarraySum".

MaxSubArraySum Method:

This method calculates the maximum subarray sum using "Kadane's Algorithm".
It takes an array of integers 'nums' as input.
If the length of the input array is 0, indicating an empty array, the method returns 0.
It initializes two variables 'maxSum' and 'currentSum' with the value of the first element of the input array.
It then iterates through the array starting from the second element.
For each element, it updates 'currentSum' by taking the maximum of the current element alone (nums[i]) and the sum of the current element and the previous 'currentSum'.
It also updates 'maxSum' to store the maximum of the previous 'maxSum' and the updated 'currentSum'.
After iterating through all elements of the array, the method returns the final 'maxSum', which represents the maximum subarray sum.

Main Method:

This is the entry point of the program.
It contains test cases to verify the correctness of the "MaxSubArraySum()" method.

JavaScript - Max Subarray Sum problem

Code:

function maxSubarraySum(nums) {
    if (nums.length === 0) {  // Check if the array is empty
        return 0;
    }
    
    let maxSum = currentSum = nums[0];  // Initialize maxSum and currentSum with first element
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);  // Update currentSum
        maxSum = Math.max(maxSum, currentSum);  // Update maxSum
    }
    return maxSum;
}

// Test Cases
console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]));  // Output: 6
console.log(maxSubarraySum([-2, -3, 4, -1, -2, 1, 5, -3]));   // Output: 7
console.log(maxSubarraySum([1, 2, 3, 4, 5]));                 // Output: 15
console.log(maxSubarraySum([-1]));                            // Output: -1
console.log(maxSubarraySum([]));                              // Output: 0

Output:

Explanation of the said JavaScript code:

maxSubarraySum Function:
This function calculates the maximum subarray sum using "Kadane's Algorithm".
It takes an array 'nums' as input.
If the length of the input array 'nums' is 0, indicating an empty array, the function returns 0.
It initializes two variables 'maxSum' and 'currentSum' with the value of the first element of the input array.
It then iterates through the array starting from the second element.
For each element, it updates 'currentSum' by taking the maximum of the current element alone (nums[i]) and the sum of the current element and the previous 'currentSum'.
It also updates 'maxSum' to store the maximum of the previous 'maxSum' and the updated 'currentSum'.
After iterating through all elements of the array, the function returns the final 'maxSum', which represents the maximum subarray sum.

Time and Space Complexity:

Time Complexity:

The code consists of a single loop that iterates over the input array 'nums' once.
Inside the loop, each iteration involves constant time operations such as comparison (max) and addition.
Therefore, the time complexity of the loop is O(n), where n is the length of the input array 'nums'.
The initial check for an empty array (if not nums) takes constant time and does not significantly affect the overall time complexity.
Thus, the overall time complexity of the "max_subarray_sum()" function is O(n).

Space Complexity:

The space complexity of the code is O(1) or constant space.
It uses a constant number of variables ('max_sum', 'current_sum', and 'num') regardless of the size of the input array.
The space required by these variables does not increase with the size of the input array.
Additionally, there are no auxiliary data structures or recursive calls that would contribute to additional space complexity.
Therefore, the space complexity of the "max_subarray_sum()" function is O(1).