SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The maxSubarraySumCircular function calculates the maximum sum of a subarray within a circular array. The circular nature of the array means that the subarray can wrap around from the end to the beginning of the array.

Intuition

To solve this problem, we need to consider both:

1. Non-Circular Subarray: The maximum subarray sum can be found using the Kadane's algorithm, which gives us the maximum sum of a subarray that doesn't wrap around.
2. Circular Subarray: For circular arrays, we can calculate the maximum subarray sum by considering the sum of the entire array minus the minimum subarray sum (which wraps around the start and end of the array).

Approach

1. Initialize Variables:

   • max_sum: Tracks the maximum subarray sum found.
   • current_max: Tracks the current maximum subarray sum ending at the current index.
   • min_sum: Tracks the minimum subarray sum found.
   • current_min: Tracks the current minimum subarray sum ending at the current index.
   • total_sum: Accumulates the sum of all elements in the array.

2. Iterate Through the Array:

   • Update current_max and max_sum to reflect the maximum subarray sum ending at the current index.
   • Update current_min and min_sum to reflect the minimum subarray sum ending at the current index.
   • Update total_sum by adding the current element.

3. Calculate the Result:

   • If total_sum equals min_sum, it means all elements are the same, and thus the maximum sum is just max_sum.
   • Otherwise, compute the maximum sum of the circular subarray as total_sum - min_sum, and return the maximum of this value and max_sum.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. We only need to make a single pass through the array.

Space Complexity:

O(1), as we are using a constant amount of extra space for variables regardless of the input size.

Code

C++

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int maxSum = INT_MIN;       // Initialize maxSum to the smallest possible integer
        int currentMax = 0;         // Variable to keep track of the current maximum subarray sum
        int minSum = INT_MAX;       // Initialize minSum to the largest possible integer
        int currentMin = 0;         // Variable to keep track of the current minimum subarray sum
        int totalSum = 0;           // Variable to keep track of the total sum of the array

        for (int num : nums) {
            currentMax = max(currentMax + num, num);
            maxSum = max(maxSum, currentMax);
            currentMin = min(currentMin + num, num);
            minSum = min(minSum, currentMin);
            totalSum += num;
        }
        return maxSum > 0 ? max(maxSum, totalSum - minSum) : maxSum;
    }
};

Python

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        max_sum = float('-inf')  # Initialize max_sum to the smallest possible value
        current_max = 0          # Variable to keep track of the current maximum subarray sum
        min_sum = float('inf')   # Initialize min_sum to the largest possible value
        current_min = 0          # Variable to keep track of the current minimum subarray sum
        total_sum = 0            # Variable to keep track of the total sum of the array

        for num in nums:
            current_max = max(current_max + num, num)
            max_sum = max(max_sum, current_max)

            current_min = min(current_min + num, num)
            min_sum = min(min_sum, current_min)

            total_sum += num

        # If total_sum is positive, consider the circular subarray sum; otherwise, return max_sum
        return max_sum if total_sum == min_sum else max(max_sum, total_sum - min_sum)

Java

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int maxSum = Integer.MIN_VALUE;  // Initialize maxSum to the smallest possible integer
        int currentMax = 0;              // Variable to keep track of the current maximum subarray sum
        int minSum = Integer.MAX_VALUE;  // Initialize minSum to the largest possible integer
        int currentMin = 0;              // Variable to keep track of the current minimum subarray sum
        int totalSum = 0;                // Variable to keep track of the total sum of the array

        for (int num : nums) {
            currentMax = Math.max(currentMax + num, num);
            maxSum = Math.max(maxSum, currentMax);

            currentMin = Math.min(currentMin + num, num);
            minSum = Math.min(minSum, currentMin);

            totalSum += num;
        }
        return maxSum > 0 ? Math.max(maxSum, totalSum - minSum) : maxSum;
    }
}

JavaScript

const maxSubarraySumCircular = function (nums) {
    let max = -Infinity;
    let currentMax = 0;
    let min = Infinity;
    let currentMin = 0;
    let total = 0;

    for (let i = 0; i < nums.length; i++) {
        currentMax = Math.max(currentMax + nums[i], nums[i]);
        max = Math.max(max, currentMax);
        currentMin = Math.min(currentMin + nums[i], nums[i]);
        min = Math.min(min, currentMin);
        total += nums[i];
    }

    return max > 0 ? Math.max(max, total - min) : max;
};