Kadane’s Algorithm in C++

Kadane’s Algorithm is used to find the subarray with the largest sum in a given array of integers. This algorithm operates in O(n) time complexity, making it very efficient for this problem.

Algorithm Explanation

The idea behind Kadane’s Algorithm is to iterate through the array while keeping track of the maximum sum of the subarray that ends at the current position. This is achieved using two variables:

• currentMax: The maximum sum of the subarray that ends at the current position.
• globalMax: The maximum sum of any subarray found so far.

For each element in the array, we update currentMax as the maximum of the current element and the sum of the current element and the previous currentMax. Then, we update globalMax as the maximum of globalMax and currentMax.

C++ Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to find the subarray with the largest sum
int findMaxSubarraySum(const vector<int>& nums) {
    // Initialize currentMax and globalMax with the first element of the array
    int currentMax = nums[0];
    int globalMax = nums[0];

    // Iterate through the array starting from the second element
    for (size_t i = 1; i < nums.size(); ++i) {
        // Update currentMax to the maximum of the current element and the sum of current element and currentMax
        currentMax = max(nums[i], currentMax + nums[i]);

        // Update globalMax if currentMax is greater than globalMax
        if (currentMax > globalMax) {
            globalMax = currentMax;
        }
    }

    // Return the globalMax which is the largest sum of subarray found
    return globalMax;
}

// Main function to test the algorithm
int main() {
    // Example array
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    // Find and print the maximum subarray sum
    int maxSubarraySum = findMaxSubarraySum(nums);
    cout << "The maximum subarray sum is: " << maxSubarraySum << endl;

    return 0;
}

Explanation of the C++ Code

In the C++ code above:

• The function findMaxSubarraySum takes a vector of integers as input and returns the sum of the subarray with the largest sum.
• We initialize currentMax and globalMax with the first element of the vector.
• We iterate through the vector starting from the second element. For each element, we update currentMax and then globalMax if necessary.
• The main function provides an example vector and calls the findMaxSubarraySum function to find and print the maximum subarray sum.

Output

For the example vector {-2, 1, -3, 4, -1, 2, 1, -5, 4}, the output will be:

The maximum subarray sum is: 6

The subarray with the largest sum is {4, -1, 2, 1} which sums to 6.