Maximum Sum Circular Subarray - C++ Solution

1. Introduction

In this blog post, we'll explore the Maximum Sum Circular Subarray problem, a variation of the classic maximum subarray problem. This problem is unique as it considers the array to be circular, which means we can also consider subarrays that wrap around.

Problem

Given a circular integer array, the task is to find a contiguous subarray that has the largest sum.

2. Solution Steps

1. Use Kadane's algorithm to find the maximum subarray sum in a non-circular (linear) array.

2. Calculate the total sum of the array.

3. Invert the signs of all elements in the array and apply Kadane's algorithm to find the maximum sum in the inverted array, which effectively finds the minimum sum subarray in the original array.

4. Subtract this minimum subarray sum from the total sum to get the maximum sum for the circular case.

5. The final answer is the maximum of the linear and circular sums found.

6. Handle the case where all numbers are negative separately.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Kadane's algorithm to find maximum subarray sum
int kadane(const vector<int>& nums) {
    int maxSum = nums[0]; // Initialize maxSum with the first element
    int currentSum = nums[0]; // currentSum also starts with the first element

    // Loop through the array starting from the second element
    for (size_t i = 1; i < nums.size(); ++i) {
        // Add the current element to the currentSum or start new subarray from current element
        currentSum = max(nums[i], currentSum + nums[i]);
        // Update maxSum if currentSum is greater
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

// Function to find the maximum circular subarray sum
int maxCircularSubArraySum(const vector<int>& nums) {
    // Step 1: Find maximum subarray sum using Kadane's algorithm
    int maxLinearSum = kadane(nums);

    // Step 2: Calculate the total sum of the array
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }

    // Step 3: Invert the signs of the elements
    for (int& num : nums) {
        num = -num;
    }

    // Step 4: Find the maximum sum in the inverted array, which is the minimum subarray sum in the original array
    int maxCircularSum = totalSum + kadane(nums);

    // Handle the case when all numbers are negative
    if (maxCircularSum == 0) {
        return maxLinearSum;
    }

    // Step 5: Return the maximum of linear and circular sums
    return max(maxLinearSum, maxCircularSum);
}

int main() {
    vector<int> nums = {2, 1, -5, 4, -3, 1, -3, 4, -1};
    cout << "Maximum Circular Subarray Sum: " << maxCircularSubArraySum(nums) << endl;
    return 0;
}

Output:

Maximum Circular Subarray Sum: 6

Explanation:

- For [2, 1, -5, 4, -3, 1, -3, 4, -1], the maximum sum circular subarray is [4, -1, 2, 1] with a sum of 6.

- For [8, -7, -3, 5, 6, -2, 3, -4, 2], the maximum sum circular subarray is [5, 6, -2, 3, -4, 2, 8] with a sum of 18.