Sponsored
Sponsored
The main idea is to use Kadane's Algorithm to find the maximum subarray sum for two scenarios: one, where the subarray wraps around the end and beginning of the array, and two, where it does not.
Calculate the maximum subarray sum using Kadane's algorithm in the normal way. Then calculate the minimum subarray sum using a similar technique but by negating the result. The maximum possible circular subarray sum will be the maximum value between the normal subarray sum and the total array sum minus the minimum subarray sum.
Time Complexity: O(n) — as both the applications of Kadane's algorithm are linear.
Space Complexity: O(1) — no additional space is used except for a few variables.
1#include <stdio.h>
2#include <limits.h>
3
4int kadane(int *arr, int n) {
5 int current_max = arr[0], global_max = arr[0];
6 for (int i = 1; i < n; i++) {
7 current_max = (arr[i] > current_max + arr[i]) ? arr[i] : current_max + arr[i];
8 global_max = (global_max > current_max) ? global_max : current_max;
9 }
10 return global_max;
11}
12
13int maxSubarraySumCircular(int* nums, int numsSize) {
14 int sum = 0, max_kadane, min_kadane;
15 for (int i = 0; i < numsSize; i++) sum += nums[i];
16
17 max_kadane = kadane(nums, numsSize);
18
19 // Inverting the sign for min kadane operation
20 for (int i = 0; i < numsSize; i++) nums[i] = -nums[i];
21 min_kadane = kadane(nums, numsSize);
22
23 int max_circular = sum + min_kadane; // sum - (-min_kadane)
24
25 // If max_circular is 0, it means all elements are negative
26 return max_circular == 0 ? max_kadane : (max_kadane > max_circular ? max_kadane : max_circular);
27}This C solution performs a similar task as the Python example but executes in a structured imperative approach. It first computes the maximum and minimum subarray sums using a modified Kadane's algorithm and calculates the potential circular maximum.
Instead of using basic Kadane's approach, we can consider computing the maximum subarray sum with additional memory for storing maximum and minimum values up to each index. This allows precise tracing of subarrays—as contiguous and potential wrap-around cases.
Time Complexity: O(n)
Space Complexity: O(1)
1#
This variation illustrates how a more verbose, manual evaluation of `max` and `min` decisions aids comprehension in languages like C. The algorithm operates by iterating through the numbers, updating cumulative totals and potential breaking points to determine the flexible subsequential approach.