최단 하위 목록> MIN

Question

예 :

난수 [1,5,1,1,3,10,5,4,2,1] 시험 소자 N=10 at index 5 및 MIN=20의 목록이 제공.

total>20와 10을 포함하여 가장 짧은 하위 목록은 분명히 total=22과 size=4와 목록 [3,10,5,4]입니다.

문제 : 효율적인 방법으로 이러한 하위 목록을 찾을 수있는 알고리즘이 무엇

?

편집 :

이

1. 상태 "짧은"을 만족하는 다른 하위 목록이있을 수 있습니다. [10,5,4,2]도 [3,10,5,4]과 유효한 결과로 짧습니다.

2. 이 질문에서 "부제"는 원래 목록의 항목 연속 블록입니다. [5,10,5,4]은 유효한 하위 목록이 아닙니다. 대신 하위 집합이라고 부릅니다.

Answer 1

다음 알고리즘은 O (N) 같아야

합계가> = 분까지 좌측 요소를 추가 갈 시험 소자부터. 이것은 서브리스트 길이 l (인덱스 i에서 시작)에 대한 첫 번째 추측을 제공합니다. 테스트 요소에 도달 할 때까지 각 단계마다 길이 l 인 하위 목록의 시작 인덱스 i를 늘리지 말고 min보다 작지 않고 하위 목록을 하나씩 줄이거 나 (오른쪽에 길이 l 줄임) 각 단계 테스트를 통해 증가시키지 마십시오.

가장자리 케이스 처리 : 왼쪽 합계가 충분하지 않거나 합계가 충분하지 않습니다. 짧은 하위 목록을 찾기

Answer 2

가> MAX가 짧은 하위 목록 <을 찾는 것과 동일 = 뒤에 이전 항목 또는 하나가 추가되는 경우 하위 목록의 총 MAX를 초과 MAX : [1,5,1,1,3,10,5,4,2,1] 및 MAX=20으로는, [1,3,10]는 포함 하위 목록입니다 10 다음에 5을 추가하면 합계가 19 < MAX이되므로 유효하지 않습니다. 첫 번째 유효한 하위 목록은 여기 [5,1,1,3,10]입니다.

알고리즘 :

1. 발견 짧은 하위 목록의 길이에 대한 marker을 만듭니다.
2. left 및 right 커서를 만듭니다.
3. 두 커서를 N으로 설정하십시오.
4. left을 왼쪽으로 while total(at left, ..., at N) <= MAX 또는 left = 0으로 이동하십시오.
   1. left > 0n - left + 1을 에 저장하십시오. 고토 6.
5. 권리 while total(at left, ..., at right) <= MAX 또는 right = list.size - 1로 이동 right.
   1. right < list.size - 1right - left + 1을 에 저장하십시오.
   2. 기타 : Return list.size.
6. 루프 while left < N and right < list.size - 1 : 오른쪽에 하나
   1. 이동 left.
   2. at right + 1 항목이있는 경우 테스트하십시오.
      1. total + at right + 1 > MAXright - left + 1을 에 저장하십시오.
      2. 오른쪽으로 오른쪽으로 한 칸 이동합니다.

어쨌든, 답을 하워드주지.