arrays - 查找总和小于给定值的最大元素(连续)？

Question

所以，我有一个所有正自然数的数组。我得到了一个阈值。我必须找出总和小于给定阈值的数字(连续)的最大计数。

For example, 
IP: arr = {3,1,2,1}
Threshold = 5

O/P: 3

输入数组的最大大小可以是 10^5。

基本上，我想到了一种算法，该算法计算原始数组子集中元素的数量，其总和将小于给定阈值。但是，它会导致 O(N^2) 的复杂性。谁能建议一个更好的算法？我不是在寻找代码，只有算法/伪代码就可以了。谢谢!

Answer 1

public static int maximumSum(int[] array, int t){
    int maxSum = 0;
    int curSum = 0;
    int start = 0;
    int end = 0;
    while(start < array.length){

        if(curSum > maxSum && curSum <= t){
            maxSum = curSum;
        }
        if(curSum <= t && end < array.length){
            curSum += array[end];
            end += 1;

        }
        else{
            curSum -= array[start];
            start+= 1;
        }
    }
    return maxSum;
}

这段代码的复杂度是 O(2 * n)，本质上是 O(n)。我想不出任何改进。