최대 평균 길이가 K (또는 그 이상) 인 서브 어레이를 찾을 수있는 O (n) 솔루션이 더 간단 할 수도 있음

Question

코딩 경쟁 사이트에서이 질문을 보았습니다.

N은 정수 배열 및 정수 K (N < = 10^5 = 1 < < K = N)를 부여하자. 길이가 k보다 큰 최대 평균을 갖는 서브 배열 (연속적)을 찾는 방법. 연구 논문에 제시된 O (n)이 솔루션이있다

(arxiv.org/abs/cs/0207026.), 중복 SO question에 연결. 저는 더 간단한 설명으로 비슷한 방법을 가지고 있다고 생각하기 때문에 이것을 별도의 질문으로 게시하고 있습니다. 아래 솔루션에 내 논리에 문제가 있다고 생각합니까? [I, J] = [0, K-1]과 같은 윈도우의 범위

1. 시작 :

   여기서 논리이다. 그런 다음 나머지 요소를 반복합니다.

2. 다음 요소마다 j에 대해 접두어 sum **을 업데이트하십시오. 이제 우리는 전체 범위 [i, j]를 사용하거나 범위 [i : j-k]를 버리고 [j-k + 1 : j]을 유지할 수 있습니다 (즉, 최신 K 요소를 유지). 더 높은 평균을 가진 범위를 선택하십시오 (O (1)에서 이것을 수행하기 위해 접두사 합계를 사용하십시오).
3. 는 모든 단계
4. 돌아 내가 배열을 반복으로

이 ** 내가 접두사 합계를 계산 끝에 최대 평균의 최대 평균 추적 할 수 있습니다. 접두사 sum i는 배열의 첫 번째 i 요소의 누적 합계입니다.

코드 :

def findMaxAverage(nums, k): 
    prefix = [0] 
    for i in range(k): 
     prefix.append(float(prefix[-1] + nums[i])) 
    mavg = prefix[-1]/k 
    lbound = -1 
    for i in range(k,len(nums)): 
     prefix.append(prefix[-1] + nums[i]) 
     cavg = (prefix[i+1] - prefix[lbound+1])/(i-lbound) 
     altavg = (prefix[i+1] - prefix[i-k+1])/k 
     if altavg > cavg: 
      lbound = i-k 
      cavg = altavg 
     mavg = max(mavg, cavg) 

    return mavg 

Answer 1

이 k = 3 및 순서를 고려하여 프로그램의

3,0,0,2,0,1,3 

출력 1.3333333333333333입니다. 하위 시퀀스 0,1,3이 발견되었지만 가능한 최상의 하위 시퀀스는 평균 1.5 인 2,0,1,3입니다.