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.
Comments
Post a Comment