小于等于K的最大子数组累加和

---

题目

请返回arr中，求子数组的累加和，是<=K的并且是最大的
返回这个最大的累加和

解题思路

假设0~ 57整体累加和1000,求< =300的累加和怎么最大
其实就是求之前有哪个前缀和是>=700且最接近

1)0-0看有没有>=700的前缀和,没有,前缀和为40
2)0-1看有没有>=700的前缀和,没有,前缀和为100
3)0-2看有没有>=700的前缀和,没有,前缀和为70
…
n)0-23前缀和为710
即24-57的累加和为小于等于300最大的累加和

用有序表存储数据,可以拿到离700最近的数字

代码

public static int getMaxLessOrEqualK(int[] arr, int K) {
    
	// 记录i之前的，前缀和，按照有序表组织
	TreeSet<Integer> set = new TreeSet<Integer>();
	// 一个数也没有的时候，就已经有一个前缀和是0了
	set.add(0);
	int max = Integer.MIN_VALUE;
	int sum = 0;
	// 每一步的i，都求子数组必须以i结尾的情况下，求个子数组的累加和，是<=K的，并且是最大的
	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); // 当前的前缀和加入到set中去
	}
	return max;

}