Python數組中一個範圍的最大和

嘗試創建一個函數，其中數組a被作爲參數傳遞，返回的是一對索引x，y，使得最大和爲sum（a [x： Y]）。例如，假設我的數組爲[4, -2, -3, 7, 3, -1]。該函數將採用這個數組並且吐出（3，4），因爲從索引3到索引4的數字序列是您可以在此數組中最大的一個序列。 10是你在這個數組中添加任何序列的最大數量。Python數組中一個範圍的最大和

這是我到目前爲止的代碼，它或多或少都有效，但對於數組長度大於10000的數組而言，這是永久的。有什麼建議麼？

def bentley(a): 
    max = 0 
    indices = 0,0 
    for x in range(len(a)): 
     for y in range(len(a)): 
      if sum(a[x:y]) > max: 
       max = sum(a[x:y]) 
       indices = x,y 
    return indices

來源

2013-11-21 PenguinProgrammer

你的問題是一個很好的理由來教自己有關的動態規劃http://stackoverflow.com/q/1065433/2282538 – Tyler

http://en.wikipedia.org/wiki/Maximum_subarray_problem

維基百科：

Kadane的算法，O（n）的

def max_subarray(A): 
    max_ending_here = max_so_far = 0 
    for x in A: 
     max_ending_here = max(0, max_ending_here + x) 
     max_so_far = max(max_so_far, max_ending_here) 

    if max_so_far > 0: 
     return max_so_far 
    else: 
     return max(A)

交替分而治之O（nlogn）：

http://penguin.ewu.edu/~bojianxu/courses/cscd320/slides_dc_2.pdf

來源

2013-11-21 17:22:53 ffledgling

我一點點一直在玩這個有點，但是，我怎麼用它來決定子陣列的起始和結束索引 – PenguinProgrammer

這是一個美味的沙拉成語：

def bentley(a): 
    return max((sum(a[x:y+1]), x, y) 
       for x, _ in enumerate(a) for y, _ in enumerate(a))[1:]

來源

2013-11-21 17:26:53 dansalmo

Python數組中一個範圍的最大和

回答

相關問題