Circular Array Subset Sum — Problem Statement & Solution Guide

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

using namespace std;

class Solution {
public:
    int maxCircularSum(vector<int>& weights, int capacity) {
        int n = weights.size();
        if (n == 0) return 0;
        
        // If all elements are negative, find the maximum single element
        // that doesn't exceed capacity
        int maxSingle = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (weights[i] <= capacity) {
                maxSingle = max(maxSingle, weights[i]);
            }
        }
        
        // If no single element fits, return the maximum single element (even if negative)
        // But the problem says non-empty segment, so we must pick at least one element
        // If all elements exceed capacity, we need to pick the least negative or smallest positive
        // Actually, if all elements > capacity, we can't pick any? 
        // Re-reading: "select a non-empty contiguous segment... whose element sum does not exceed capacity"
        // If no single element <= capacity, then no valid segment exists? 
        // But the problem implies there's always a solution. Let's assume at least one element <= capacity.
        
        // Use sliding window on doubled array
        // We want max sum <= capacity for a contiguous subarray in circular array
        // This is equivalent to finding max sum <= capacity in array of size 2n, 
        // but window length <= n
        
        int maxSum = maxSingle;
        int left = 0;
        int currentSum = 0;
        
        for (int right = 0; right < 2 * n; right++) {
            currentSum += weights[right % n];
            
            // Shrink window if sum exceeds capacity or window size >= n
            while (left <= right && (currentSum > capacity || right - left + 1 > n)) {
                currentSum -= weights[left % n];
                left++;
            }
            
            if (currentSum <= capacity) {
                maxSum = max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
};

int main() {
    vector<int> weights = {4, 2, 1, 7, 3};
    int capacity = 10;
    Solution sol;
    cout << sol.maxCircularSum(weights, capacity) << endl;
    return 0;
}

import java.util.*;

class Solution {
    public int maxCircularSum(int[] weights, int capacity) {
        int n = weights.length;
        if (n == 0) return 0;
        
        // Find max single element that fits
        int maxSingle = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (weights[i] <= capacity) {
                maxSingle = Math.max(maxSingle, weights[i]);
            }
        }
        
        // Sliding window on doubled array
        int maxSum = maxSingle;
        int left = 0;
        int currentSum = 0;
        
        for (int right = 0; right < 2 * n; right++) {
            currentSum += weights[right % n];
            
            while (left <= right && (currentSum > capacity || right - left + 1 > n)) {
                currentSum -= weights[left % n];
                left++;
            }
            
            if (currentSum <= capacity) {
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
    
    public static void main(String[] args) {
        int[] weights = {4, 2, 1, 7, 3};
        int capacity = 10;
        Solution sol = new Solution();
        System.out.println(sol.maxCircularSum(weights, capacity));
    }
}

from typing import List

class Solution:
    def maxCircularSum(self, weights: List[int], capacity: int) -> int:
        n = len(weights)
        if n == 0:
            return 0
        
        # Find max single element that fits
        max_single = float('-inf')
        for i in range(n):
            if weights[i] <= capacity:
                max_single = max(max_single, weights[i])
        
        # Sliding window on doubled array
        max_sum = max_single
        left = 0
        current_sum = 0
        
        for right in range(2 * n):
            current_sum += weights[right % n]
            
            while left <= right and (current_sum > capacity or right - left + 1 > n):
                current_sum -= weights[left % n]
                left += 1
            
            if current_sum <= capacity:
                max_sum = max(max_sum, current_sum)
        
        return max_sum

# Example driver code
if __name__ == "__main__":
    weights = [4, 2, 1, 7, 3]
    capacity = 10
    sol = Solution()
    print(sol.maxCircularSum(weights, capacity))

/**
 * @param {number[]} weights
 * @param {number} capacity
 * @return {number}
 */
var maxCircularSum = function(weights, capacity) {
    const n = weights.length;
    if (n === 0) return 0;
    
    // Find max single element that fits
    let maxSingle = -Infinity;
    for (let i = 0; i < n; i++) {
        if (weights[i] <= capacity) {
            maxSingle = Math.max(maxSingle, weights[i]);
        }
    }
    
    // Sliding window on doubled array
    let maxSum = maxSingle;
    let left = 0;
    let currentSum = 0;
    
    for (let right = 0; right < 2 * n; right++) {
        currentSum += weights[right % n];
        
        while (left <= right && (currentSum > capacity || right - left + 1 > n)) {
            currentSum -= weights[left % n];
            left++;
        }
        
        if (currentSum <= capacity) {
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    
    return maxSum;
};

// Example driver code
const weights = [4, 2, 1, 7, 3];
const capacity = 10;
console.log(maxCircularSum(weights, capacity));