Maximum subarray cumulative sum less than or equal to K

---

subject

Please return arr in , Find the cumulative sum of subarrays , yes <=K And is the largest
Returns the maximum cumulative sum

Their thinking

hypothesis 0~ 57 Total cumulative sum 1000, seek < =300 How to maximize the cumulative sum of
In fact, it is to find which prefix and is before >=700 And closest to

1)0-0 See if there is >=700 And , No, , Prefixes and are 40
2)0-1 See if there is >=700 And , No, , Prefixes and are 100
3)0-2 See if there is >=700 And , No, , Prefixes and are 70
…
n)0-23 Prefixes and are 710
namely 24-57 The cumulative sum of is less than or equal to 300 Maximum cumulative sum

Store data in an ordered table , You can get away 700 Recent figures

Code

public static int getMaxLessOrEqualK(int[] arr, int K) {
    
	//  Record i Previous , The prefix and , Organize according to the order table 
	TreeSet<Integer> set = new TreeSet<Integer>();
	//  When there is no number , There is already a prefix and is 0 了 
	set.add(0);
	int max = Integer.MIN_VALUE;
	int sum = 0;
	//  Every step of i, All subarrays must be i At the end of the story , Find the cumulative sum of subarrays , yes <=K Of , And it's the biggest 
	for (int i = 0; i < arr.length; i++) {
    
		sum += arr[i]; // sum -> arr[0..i];
		if (set.ceiling(sum - K) != null) {
    
			max = Math.max(max, sum - set.ceiling(sum - K));
		}
		set.add(sum); //  The current prefix and add to set In the middle 
	}
	return max;

}