Максимальный непрерывный поддиапазон (с большим количеством элементов)

Question

Учитывая массив натуральных чисел и другой естественный T, как найти смежный подмассив с суммой, меньшей или равной T, но число элементов в этом подмассиве максимальна?

Например, если данный массив:

{3, 1, 2, 1, 1} и T = 5. Тогда максимальное contigous подмассив является {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). Я не проверял это, но это выглядит нормально:

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 Я думаю, вы можете найти вдохновение с существующими алгоритмами.