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; }
Leave a Comment