14 未排序数组中累加和小于或等于给定值的最长子数组长度
Table of Contents

ac

import java.util.*;

public class Main {

    public static Scanner sc = new Scanner(System.in);

    /**
     * 二分法找到第一个大于等于 val 的位置
     */
    public static int bsearch(int[] arr, int left, int right, int val){
        int pos = -1;
        while(left <= right){
            int mid = ( right - left ) / 2 + left;
            if(arr[mid] >= val){
                pos = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return pos;
    }

    public static void main(String[] args) {

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] sums = new int[n+1];
        int[] helps = new int[n+1];
        sums[0] = 0;
        helps[0] = 0;
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            int val = sc.nextInt();
            arr[i] = val;
            sums[i + 1] = sums[i] + arr[i];
            helps[i + 1] = Math.max(helps[i], sums[i+1]);

        }
        int res = 0;
        // 以 i位置 结尾的 判断,每次判断二分法即可
        for(int i=0;i<n;i++){
            int sumsTmpI = sums[i+1];
            if(sumsTmpI <= k){
                int len = i + 1;
                res = Math.max(res, len);
            }else {
                int tmpVal = sumsTmpI - k;
                int pos = bsearch(helps, 1, i, tmpVal);
                int len = 0;
                if(pos != -1){
                    len = i - (pos - 1);
                }
                res = Math.max(res, len);
            }
        }

        System.out.println(res);
    }

}