Untitled

public class MaxSumSubarrayLessThanK {
    public static int maxSumSubarrayLessThanK(int[] arr, int K) {
        TreeSet<Integer> prefixSums = new TreeSet<>();
        prefixSums.add(0);
        
        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;

        for (int num : arr) {
            currentSum += num;
            
            // Find the smallest prefix sum that is strictly greater than (currentSum - K)
            Integer prefixSum = prefixSums.higher(currentSum - K);
            if (prefixSum != null) {
                maxSum = Math.max(maxSum, currentSum - prefixSum);
            }
            
            prefixSums.add(currentSum);
        }

        return maxSum;
    }

  
}


// using ceiling
public class MaxSumSubarrayLessThanK {
    // Main function to find maximum sum subarray less than K
    public static int maxSumSubarrayLessThanK(int[] arr, int K) {
        if (arr == null || arr.length == 0) {
            return Integer.MIN_VALUE;
        }

        // Check if K is less than minimum element
        int minElement = arr[0];
        for (int num : arr) {
            minElement = Math.min(minElement, num);
        }
        if (K <= minElement) {
            return Integer.MIN_VALUE;
        }

        // Using TreeSet to maintain prefix sums
        TreeSet<Integer> prefixSums = new TreeSet<>();
        prefixSums.add(0);  // Add 0 to handle the case when entire subarray sum is less than K
        
        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;

        for (int num : arr) {
            currentSum += num;
            
            // Find the largest prefix sum that makes currentSum - prefixSum < K
            Integer prefixSum = prefixSums.ceiling(currentSum - K + 1);
            if (prefixSum != null) {
                maxSum = Math.max(maxSum, currentSum - prefixSum);
            }
            
            prefixSums.add(currentSum);
        }

        return maxSum;
    }