最大連續子數組（最多元素數）

Question

給定一個自然數和另一個自然數T的數組，如何找到sum小於或等於T的連續子數組，但是這個子數組中的元素數是最大化？

例如，如果給定的數組是：

{3, 1, 2, 1, 1}和T = 5。那麼最大連續子數組是{1, 2, 1, 1}，因爲它將包含5個元素並且總和等於5.

另一個示例：{10,1,1,1,1,3,6,7}與T = 8。然後最大連續子陣是${1,1,1,1,3}$

我可以用O(n^2)操作。不過，我正在尋找這個問題的線性時間解決方案。有任何想法嗎？

Answer 1

應該可以用O（n）來做到這一點。我沒有測試這一點，但它看起來OK：

int start = 0, end = 0; 
int beststart = 0, bestend = 0; 
int sum = array[0]; 

while (end + 1 < arraysize) { 
    if (array[end + 1] + sum <= T) 
    sum += array[end++]; 
    else 
    sum -= array[start++]; 
    if ((end - start) > (bestend - beststart)) { 
    beststart = start; 
    bestend = end; 
    } 
} 

所以，基本上，它移動的滑動窗口沿陣列並記錄其end - start是最大的點。

Answer 2

它似乎是最大的子數組問題的上限版本：http://en.wikipedia.org/wiki/Maximum_subarray_problem 我想你可以找到現有算法的靈感。