查找总和小于给定值的最大元素（连续）？

所以，我有一个所有积极的自然数的数组。我给了一个门槛值。我必须找出总和小于给定阈值的最大数字（连续）。查找总和小于给定值的最大元素（连续）？

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

O/P: 3

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

基本上，我想到了一种算法，该算法计算原始数组子集中元素的数量，其总和将小于给定的阈值。但是，这会导致O（N^2）的复杂性。任何人都可以提出更好的算法？我没有在寻找代码，只有算法/伪代码才能正常工作。谢谢！

来源

2015-06-15 John Lui

尝试以下...

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 
    } 
}

希望这有助于你...

请让我知道如果您有任何进一步的问题...

来源

2015-06-15 08:53:58

但它不会返回最大数量。例如，如果输入数组是'6 1 2 3'和'threshold = 5'，那么当它返回'2'时，你的代码将返回'1'。 –

为6 1 2 3和阈值5，最大计数是6是正确的？...它会怎样7 –

这将是一个有点粗糙，但应该指向O（n）解决方案

用两个指针遍历列表，我们从一开始就调用一个导致，另一个导致跟踪，因为导致和一条小路。

记录从追踪到引导的总和;以及当前遇到的最长有效序列的长度。

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

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

继续，直到前导指针到达末尾。

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

来源

2015-06-15 08:56:30 moreON

我实现了你所说的，并且我编辑了我原来的帖子以包含代码。但是，如果阈值非常大（8位数字），并且数组中的元素数量为“100000”，则它仍然会超出时间限制。你能告诉我怎样才能进一步优化我的代码？ –

不要重复计算总和。利用从Ai到Aj的总和等于从Ai到Aj-1 + A的总和的事实 – moreON

我会尝试如下：

开始从数组开头的元素相加，直到达到阈值。保存这个子数组作为临时结果。
然后从子阵列的开头删除一个元素，并尝试从另一侧添加新元素，直到再次达到阈值。如果结果更大，则将新结果替换为以下结果。
继续，直到数组结束。

来源

2015-06-15 08:56:46 MaMazav

这听起来与我们在几乎相同时间发布的解决方案完全相同。这给了我更多的信心。 – moreON

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）。我想不出有什么改进。

来源

2016-11-03 20:14:50

查找总和小于给定值的最大元素（连续）？

回答

相关问题