子数组累加和小于等于K的最大长度
给定一个整数组成的无序数组arr，值可能正、可能负、可能0
给定一个整数值K
找到arr的所有子数组里，哪个子数组的累加和<=K，并且是长度最大的
返回其长度
// 给定数组arr, 返回子数组累加和<=k的最大长度
public int maxLength(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
int N = arr.length;
// minSum[i]已i下标开头的所有子数组的最小累加和
int[] minSum = new int[N];
// minSumEnd[i]取得已i下标开头的所有子数组的最小累加和时, 子数组结尾位置
int[] minSumEnd = new int[N];
minSum[N - 1] = arr[N - 1];
minSumEnd[N - 1] = N - 1;
for (int i = N - 2; i >= 0; i--) {
if (minSum[i + 1] > 0) {
minSum[i] = arr[i];
minSumEnd[i] = i;
} else {
minSum[i] = arr[i] + minSum[i + 1];
minSumEnd[i] = minSumEnd[i + 1];
}
}
int ans = 0, r = 0, sum = 0;
for (int i = 0; i < N; i++) {
while (r < N && sum + minSum[r] <= k) {
sum += minSum[r];
r = minSumEnd[r] + 1;
}
ans = Math.max(ans, r - i);
if (r > i)
sum -= arr[i];
else
r++;
}
return ans;
}