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

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）。我想不出对此有任何改进。

Answer 2

这会有点粗糙，但应该指向 O（n） 解决方案

使用两个指针遍历列表，这两个指针都从头开始，我们将一个称为线索，另一个称为跟踪，因为一个领先，一个跟踪。

跟踪从跟踪到线索的总和;以及当前遇到的最长有效序列的长度。

当当前总和小于（或等于）阈值时，前进引导指针并通过添加它现在指向的值来调整总和。如果总和仍然小于（或等于）阈值，则从尾迹到线索的序列是可能的。

当当前总和大于阈值时，请前进跟踪指针。

继续，直到引导指针到达终点。

您需要填写详细信息并仔细实施，但对我来说似乎足够合理。

Answer 3

我会尝试以下方法：

• 首先对数组开头的元素求和，直到达到阈值。将此子数组另存为临时结果。
• 然后从子数组的开头删除一个元素，并尝试从另一端添加新元素，直到再次达到阈值。如果结果较大，请将以下结果替换为新结果。
• 继续直到阵列结束。

Answer 4

试试下面...

public int maximumElem(int[] array,int threshold)
{
   int sum = 0;
   for(int i=0;i<array.length;i++)
   {
     sum = sum + array[i]; //sum the values at each index
     if(sum >= threshold)  //check condition
       return (i+1); // if sum is reaching the threshold then return the index
   }
}

希望这对您有所帮助...

如果您有任何其他问题，请告诉我...