查找總和小於給定值的最大元素（連續）？

所以，我有一個所有積極的自然數的數組。我給了一個門檻值。我必須找出總和小於給定閾值的最大數字（連續）。查找總和小於給定值的最大元素（連續）？

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

查找總和小於給定值的最大元素（連續）？

回答

相關問題