Kadane의 알고리즘, 연속 요소의 최대 합계

Question

연속 최대 연속 문제의 시작 인덱스를 어떻게 추적 할 수 있습니까?

index_pairs[]은 시작 색인 [0]이고 끝 색인 [1]은 최대 연속입니다. 합집합.

나는 항상 최대 연속 요약의 마지막 인덱스를 찾을 수 있지만, maxsum 후 더 많은이있는 경우 내 시작 인덱스는 index_pairs[0]는 잘못된 인덱스를 반환합니다.

생각의 나의 기차

: maxendinghere가 내 iterable 목록의 정수로 0에서 추가 될 때 시작 인덱스의 합을 알기 위해, 나는 를 알고 있어야합니다. 그러나 maxendinghere가 0보다 작 으면 0이되고 다음 연속 0이합계 (최대 합계가 아닐 수도 있음)가 합산 되더라도 업데이트됩니다.

---

from random import randrange 
iterable = [randrange(-10,10) for r in xrange(100)] 

def max_continuous_sequence(iterable): 
    maxsum, maxendinghere = 0, 0 
    index_pairs = [0,0] 
    for i,x in enumerate(iterable): 
     # summing next numbers 
     maxendinghere += x 
     if maxsum < maxendinghere: 
      # found a higher sum 
      maxsum = maxendinghere 
      index_pairs[1] = i 
     elif maxendinghere < 0: 
      # resets the max here if next element is less than zero 
      maxendinghere = 0 
      # starts off the index at where we ended last 
      index_pairs[0] = i+1 
    return (index_pairs[0],index_pairs[1]) 

Answer 1

당신은 요소의 순서를 반대로 수있는 정말이다 (마지막 인덱스를 계산하는 알고리즘을 실행 내 최대 연속 합계 지수의 시작 인덱스를 찾을 수있는 방법이 있나요 초기 시퀀스의 첫 번째 인덱스)를 계산 한 다음 시퀀스 끝에서부터 응답을 얻기까지의 거리를 계산합니다. 추가는 교환 가능합니다.