Kadane算法，連續元素的最大求和

index_pairs[]是起始索引[0]和結束索引[1]的最大值。和。

我總能找到的最大連續總和的最後一個索引，但我的出發指數，index_pairs[0]將返回不正確的指標，如果有是maxsum後一個更大的數字。

我的思路：爲了知道起始索引的總和，我必須知道時maxendinghere從零我iterable名單的整數增加。但是，如果最大值總是小於零，並且即使下一個連續的總和（可能不是最大總和）被更新，它也將始終爲零。

有沒有辦法找到我的最大連續求和指數的起始索引

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])

來源

2013-11-23 lzc

你可以扭轉元素的順序，運行算法來計算最後一個索引（這是真的初始序列的第一個索引），然後計算它距序列末尾的距離以獲得答案。加法是可交換的:)

來源

2013-11-23 01:44:25 mattnedrich

Kadane算法，連續元素的最大求和

回答

相關問題