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

这个O(N)时间复杂度的优化方案简直是毁***地级别的

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        // minSums[i]表示从i开始,往后数组的最小和;minSumEnds[i]表示这个最小和数组的边界
        int[] minSums = new int[n], minSumEnds = new int[n];
        minSums[n - 1] = arr[n - 1];
        minSumEnds[n - 1] = n - 1;
        for(int i = n - 2; i >= 0; i--){
            if(minSums[i + 1] < 0){
                // 右边是负贡献，直接累加上
                minSums[i] = arr[i] + minSums[i + 1];
                minSumEnds[i] = minSumEnds[i + 1];
            }else{
                minSums[i] = arr[i];
                minSumEnds[i] = i;
            }
        }
        int end = 0, sum = 0, maxLen = 0;
        for(int i = 0; i < n; i++){
            while(end < n && sum + minSums[end] <= k){
                // 满足累加和小于等于k就累加上
                sum += minSums[end];
                end = minSumEnds[end] + 1;
            }
            maxLen = Math.max(maxLen, end - i);
            if(end > i){
                sum -= arr[i];      // 窗口内还有救，把左边的元素弹出去试试
            }else{
                end = i + 1;        // 窗口内没救了，另起一个起点
            }
        }
        System.out.println(maxLen);
    }
}

借鉴已有思路：先获取每个位置的h[n]数组：从当前位置开始累加的最小值，end[n]数组：h[n]最小值得位置。然后从头开始循环数组：每个位置为左边界，也就是说，当前位置为最长序列的开始。

import java.util.*;
public class Main
{
    public static int getMaxLen(int []arr,int target)
    {
        if(arr==null||arr.length==0)
        {
            return 0;
        }
        int maxLen=0,sum=0,endCur=0,n=arr.length;
        int []h=new int[n];
        int []end=new int[n];
        h[n-1]=arr[n-1];end[n-1]=n-1;//初始化数组  h[n]为从当前位置开始往后加的最小值 end[n]记录加到最小值的位置
        for(int i=n-2;i>=0;i--)//初始化数组
        {
            if(h[i+1]<=0)
            {
                h[i]=h[i+1]+arr[i];
                end[i]=end[i+1];
            }
            else {
                h[i]=arr[i];
                end[i]=i;
            }
        }
        //求返回值：从头开始遍历，每个位置为左边界
        for(int i=0;i<n;i++)
        {
            sum=h[i];endCur=i;
            while(endCur<n&&sum<=target)
            {
                endCur=end[endCur]+1;
                if(endCur<n)
                {
                    sum=sum+h[endCur];
                }
                
            }
            maxLen=Math.max(maxLen, endCur-i);
            
        }
        return maxLen;
    }
    public static void main(String[]args)
    {
        Scanner in=new Scanner(System.in);
        int N=in.nextInt(),k=in.nextInt();
        int []arr=new int[N];
        for(int i=0;i<N;i++)
        {
            arr[i]=in.nextInt();
        }
        System.out.println(getMaxLen(arr,k));
    }
}