Maximum Subarray Sum - Naukri Code 360

Introduction

Maximum subarray sum is a fundamental problem in computer science & programming. It involves finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum. This problem has important applications in fields like finance, bioinformatics & image processing.

In this article, we'll explore the problem statement, Kadane's algorithm for solving it, illustrations of how the algorithm works, & implementations in various programming languages. We'll also discuss the time & space complexity of the algorithm.

Problem Statement

The maximum subarray sum problem asks us to find the largest possible sum of a contiguous subsequence in an array or list of integers. This can range from a single number to the sum of the entire array, and the values within the array can be both positive & negative. This problem is not just academic but also practical, as it appears in various real-world scenarios, such as analyzing financial data or finding the most productive time span in a sequence of operations.

For example, consider the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The subarray with the maximum sum is [4, -1, 2, 1], which adds up to 6.

Our objective is to develop an efficient way to find this sum in any given list of numbers. We'll look at different methods to solve this, each varying in complexity & efficiency.

Pseudocode of Kadane's Algorithm

Kadane's Algorithm is a clever approach that efficiently finds the maximum sum of a contiguous subarray. Here's the pseudocode to understand how it operates, providing a step-by-step method that scans through the entire array, keeping track of the maximum sum found so far.

Initialize:

max_current = 0
  max_global = -infinity
For each element x in the array:
  max_current = max(x, max_current + x)
  if max_current > max_global:
    max_global = max_current
Return max_global

Initialize Variables: Start with max_current set to 0, which will store the sum of the current subarray. max_global is initialized to a very small number to ensure it gets updated in the first iteration.
Iterate Through the Array: For each element x, update max_current. It is set to the greater of x itself or the sum of x and the previous max_current. This decision checks if adding x to the existing subarray yields a higher sum than starting a new subarray with x.
Update Global Maximum: If max_current exceeds max_global, then update max_global. This keeps track of the highest sum encountered so far across all subarrays considered.
Result: After processing all elements, max_global will hold the maximum sum of any contiguous subarray.

This algorithm is powerful because it efficiently computes the maximum subarray sum with a single scan through the array, making it faster than brute force methods.

Illustration of Kadane's Algorithm

To better understand how Kadane's Algorithm works, let's apply it to a specific example. Consider the array [3, -2, 5, -1, 6, -3, 2, 8, -4, 5]. We'll go through each step of the algorithm to see how it finds the maximum subarray sum.

Step-by-Step Execution:

Start: max_current = 0, max_global = -infinity.
Element 1 (3): max_current = max(3, 0 + 3) = 3. Update max_global = 3.
Element 2 (-2): max_current = max(-2, 3 - 2) = 1. No change to max_global.
Element 3 (5): max_current = max(5, 1 + 5) = 6. Update max_global = 6.
Element 4 (-1): max_current = max(-1, 6 - 1) = 5. No change to max_global.
Element 5 (6): max_current = max(6, 5 + 6) = 11. Update max_global = 11.
Element 6 (-3): max_current = max(-3, 11 - 3) = 8. No change to max_global.
Element 7 (2): max_current = max(2, 8 + 2) = 10. No change to max_global.
Element 8 (8): max_current = max(8, 10 + 8) = 18. Update max_global = 18.
Element 9 (-4): max_current = max(-4, 18 - 4) = 14. No change to max_global.
Element 10 (5): max_current = max(5, 14 + 5) = 19. Update max_global = 19.

After processing all elements, the algorithm determines that the maximum subarray sum is 19, achieved by the subarray [3, -2, 5, -1, 6, -3, 2, 8, -4, 5].

This example clearly demonstrates the algorithm's process of dynamically deciding whether to add the current element to the existing subarray or start a new subarray, and efficiently finding the maximum sum possible.

Implementation of Kadane’s Algorithm in Various Programming Languages

Python
Java
C++

Python

def max_subarray_sum(arr):
    max_current = max_global = arr[0]
    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])
        if max_current > max_global:
            max_global = max_current
    return max_global

You can also try this code with Online Python Compiler

Run Code

Java

public class Main {
    public static int maxSubarraySum(int[] arr) {
        int maxCurrent = arr[0];
        int maxGlobal = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
            if (maxCurrent > maxGlobal) {
                maxGlobal = maxCurrent;
            }
        }
        return maxGlobal;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, -3, 2, 1, -1};
        System.out.println("Maximum subarray sum is " + maxSubarraySum(nums));
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>
#include <algorithm> // For std::max

int maxSubarraySum(const std::vector<int>& arr) {
    int maxCurrent = arr[0], maxGlobal = arr[0];
    
    for (size_t i = 1; i < arr.size(); i++) {
        maxCurrent = std::max(arr[i], maxCurrent + arr[i]);
        if (maxCurrent > maxGlobal) {
            maxGlobal = maxCurrent;
        }
    }
    return maxGlobal;
}

int main() {
    std::vector<int> nums = {1, -3, 2, 1, -1};
    std::cout << "Maximum subarray sum is " << maxSubarraySum(nums) << std::endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Maximum subarray sum is 3

Time & Space Complexity of Kadane’s Algorithm

When evaluating any algorithm, understanding its efficiency in terms of time and space is crucial. For Kadane's Algorithm, these aspects are especially significant because they highlight why the algorithm is favored for problems involving subarray sums.

Time Complexity

The time complexity of Kadane’s Algorithm is O(n), where n is the number of elements in the input array. This efficiency stems from the fact that the algorithm only needs to traverse the array once. During this single pass, it calculates the maximum subarray sum by continuously updating the current maximum sum and the global maximum sum at each step. This linear time complexity makes Kadane's Algorithm highly efficient and suitable for large datasets.

Space Complexity

The space complexity of Kadane’s Algorithm is O(1). This is because the algorithm maintains only a few variables (typically max_current and max_global) regardless of the size of the input array. It does not require any additional space that scales with the input size, making it extremely memory efficient.

These characteristics make Kadane’s Algorithm an optimal choice for finding the maximum subarray sum, as it provides a perfect balance between time efficiency and low memory usage.

Print the Largest Sum Contiguous Subarray

After determining the maximum sum of a contiguous subarray using Kadane's Algorithm, it might also be useful to know which elements compose this optimal subarray. This section explains how to modify the basic Kadane’s Algorithm to not only find the maximum sum but also print the elements of the subarray that contribute to this sum.

Modifying the Algorithm

To achieve this, we'll need to keep track of the start and end indices of the best subarray. Here’s how you can implement this in Python, demonstrating the modifications to store these indices:

Python

Python

def max_subarray_sum_with_indices(arr):
    max_current = max_global = arr[0]
    start = end = s = 0

    for i in range(1, len(arr)):
        if arr[i] > max_current + arr[i]:
            max_current = arr[i]
            s = i
        else:
            max_current += arr[i]

        if max_current > max_global:
            max_global = max_current
            start = s
            end = i

    return max_global, arr[start:end + 1]

# Example array
arr = [3, -2, 5, -1, 6, -3, 2, 8, -4, 5]
max_sum, subarray = max_subarray_sum_with_indices(arr)
print("Maximum Subarray Sum:", max_sum)
print("Subarray:", subarray)

You can also try this code with Online Python Compiler

Run Code

Output

Maximum Subarray Sum: 19
Subarray: [3, -2, 5, -1, 6, -3, 2, 8, -4, 5]

Explanation:

Variables start, end, and s: These are used to track the indices. s is the potential starting point of a new subarray.
Condition Check: Each element is checked to see if it should start a new subarray or continue the current one.
Updating Indices: When max_current sets a new record for max_global, update the start and end to the current values of s and i.

This modification allows the algorithm not only to return the maximum sum but also the subarray that yields this sum, providing full insight into the solution's details.

Largest Sum Contiguous Subarray Using Dynamic Programming

Dynamic programming (DP) is another approach to solve the maximum subarray sum problem, offering a systematic way to find solutions to subproblems & building up to the solution of the overall problem. This method is particularly useful when you need to retrace the solution, not just calculate the maximum sum.

DP Approach Explained

Dynamic programming solves problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid computing the same results multiple times. For the maximum subarray sum, dynamic programming can be implemented by using an array where each element represents the maximum subarray sum ending at that position.

Here’s how you can implement this in Python:

def max_subarray_sum_dp(arr):
    n = len(arr)
    dp = [0]*n  # dp[i] will be the max subarray sum ending at index i
    dp[0] = arr[0]
    max_sum = dp[0]
    for i in range(1, n):
        dp[i] = max(dp[i-1] + arr[i], arr[i])
        max_sum = max(max_sum, dp[i])
    return max_sum

Key Points:

Initialization: Start by setting the first element of the DP array to the first element of the input array, as the only subarray ending at the first index is the element itself.
Recurrence Relation: For each subsequent element, determine if it is better to add the current element to the maximum sum subarray found so far, or start a new subarray with the current element. This decision is made using max(dp[i-1] + arr[i], arr[i]).
Compute Maximum Sum: Continuously update the max_sum with the maximum value found in the DP array.

Implementation of Largest Sum Contiguous Subarray Using Dynamic Programming in Various Programming Languages

Python
Java
C++

Python

def max_subarray_sum_dp(arr):
    if not arr:
        return 0
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# Example usage
arr = [3, -2, 5, -1, 6, -3, 2, 8, -4, 5]
print("Maximum Subarray Sum:", max_subarray_sum_dp(arr))

You can also try this code with Online Python Compiler

Run Code

Java

public class MaxSubarraySum {
    public static int maxSubarraySumDP(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int maxSum = arr[0], currentSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {3, -2, 5, -1, 6, -3, 2, 8, -4, 5};
        System.out.println("Maximum Subarray Sum: " + maxSubarraySumDP(arr));
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>
#include <algorithm> // For std::max

int maxSubarraySumDP(const std::vector<int>& arr) {
    if (arr.empty()) return 0;
    int maxSum = arr[0], currentSum = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        currentSum = std::max(arr[i], currentSum + arr[i]);
        maxSum = std::max(maxSum, currentSum);
    }
    return maxSum;
}

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

You can also try this code with Online C++ Compiler

Run Code

Output

Maximum Subarray Sum: 19

Each of these implementations demonstrates how the dynamic programming approach can be tailored to work efficiently across different programming environments, providing a clear and direct solution to finding the largest sum of a contiguous subarray.

Frequently Asked Questions

Why is Kadane's Algorithm better than the naive approach?

Kadane's Algorithm is preferred because it operates in O(n) time, making it significantly faster than the naive approach, which has a time complexity of O(n^2) due to its requirement to consider every possible subarray.

Can Kadane's Algorithm handle arrays with all negative numbers?

Yes, Kadane’s Algorithm can handle arrays consisting entirely of negative numbers. It will return the largest single element, as this constitutes the maximum sum subarray in such cases.

How does dynamic programming differ from other algorithms in solving this problem?

Dynamic programming is particularly effective for the maximum subarray sum problem because it breaks down the problem into manageable subproblems, solving each just once & storing their solutions. This avoids the redundant calculations typical of other brute-force methods, leading to more efficient solutions.

Conclusion

In this article, we have learned about the maximum subarray sum problem and explored different methods to solve it, including Kadane's Algorithm and dynamic programming. We discussed the theory behind these algorithms, provided pseudocode, and demonstrated practical implementations in multiple programming languages. We have seen how to efficiently find and understand the largest sum of contiguous subarray elements within a given array, using both algorithmic techniques and dynamic programming approaches.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.