최대 인접한 하위 배열 (대부분의 요소가있는 경우)

Question

자연수와 다른 자연 T의 배열이있는 경우 합계가 T보다 작거나 같은 연속적인 부분 배열을 찾는 방법은 있지만이 하위 배열의 요소 수는 최대화?

는 예를 들어, 특정 배열 인 경우

T = 5 및

{3, 1, 2, 1, 1}. 그럼 5 개 요소를 포함하기 때문에 최대 인접하게 서브 어레이는 {1, 2, 1, 1}이며 합계 5

다른 예와 같다 : T = 8와 {10,1,1,1,1,3,6,7}. 그렇다면 최대 연속 배열은 ${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 기존 알고리즘으로 영감을 얻을 수있을 것 같습니다.