Kadane's Algorithm in C++: A Comprehensive Guide

AyoubGharbi | Feb 2, 2022 min read

Subarray problems are a common and important part of computer science and software engineering. One such problem is finding the maximum sum subarray in a given input array. Kadane’s Algorithm is a well-known solution to this problem and is widely used in industry and academia. In this article, we’ll be exploring Kadane’s Algorithm in detail, using C++ as our implementation language.

1- Understanding the Problem

The problem of finding the maximum sum subarray can be stated as follows: given an input array of integers, your goal is to find the contiguous subarray with the largest sum. For example, if the input array is [−2, 1, −3, 4, −1, 2, 1, −5, 4], the maximum sum subarray is [4, −1, 2, 1], which has a sum of 6.

2- Understanding Kadane’s Algorithm

Kadane’s Algorithm is a dynamic programming approach to solving the maximum sum subarray problem. The algorithm keeps track of the current sum of subarray elements and compares it to the maximum sum of all subarrays. If the current sum is greater than the maximum sum, the maximum sum is updated. The algorithm then repeats this process for all subarrays in the input array, ultimately returning the maximum sum.

3- Implementing Kadane’s Algorithm in C++

Let’s take a look at a sample implementation of Kadane’s Algorithm in C++:

#include <iostream>
#include <vector>

int maxSubarraySum(std::vector<int>& nums) {
    int max_sum = nums[0];
    int current_sum = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        current_sum = std::max(nums[i], current_sum + nums[i]);
        max_sum = std::max(max_sum, current_sum);
    }
    return max_sum;
}

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

In this code, we’ve defined the maxSubarraySum function, which takes a vector of integers as input and returns the maximum sum of subarray elements. The function first initializes the variables max_sum and current_sum to the first element of the input array. We then traverse the input array using a loop and keep track of the current sum of subarray elements. If the current sum is greater than the maximum sum, we update the maximum sum. Finally, the function returns the maximum sum.

4- Explaining the Algorithm

The core of the algorithm lies in the loop, which traverses the input array and keeps track of the current sum of subarray elements. Let’s take a closer look at what’s happening in the loop:

current_sum = std::max(nums[i], current_sum + nums[i]);

This line of code updates the current sum of subarray elements. The max function returns the greater of two values, so in this case, we’re choosing the maximum of the current element of the input array and the current sum plus the current element. This is because we want to ensure that the current sum is positive, as negative sums won’t contribute to the maximum sum. If the current sum plus the current element is negative, we start a new subarray with the current element.

max_sum = std::max(max_sum, current_sum);

This line of code updates the maximum sum. If the current sum is greater than the maximum sum, we update the maximum sum. This ensures that the maximum sum is always up to date as we traverse the input array.

5- Conclusion

Kadane’s Algorithm is a simple and efficient solution to the maximum sum subarray problem. With its dynamic programming approach, it’s well suited to solving real-world subarray problems and has a time complexity of O(n), making it an excellent choice for large input arrays. We hope this article has provided a comprehensive overview of Kadane’s Algorithm and its implementation in C++. Happy coding!