返回最大子列表的總和

我必須編寫一個函數，它接受一個整數列表並返回列表的最大總和子列表。一個例子是：返回最大子列表的總和

l = [4,-2,-8,5,-2,7,7,2,-6,5]

回報19

到目前爲止我的代碼是：

count = 0 
for i in range(0,len(l)-1): 
    for j in range(i,len(l)-1): 
     if l[i] >= l[j]: 

      count += l[i:j] 

return count

我有點卡住和困惑，誰能幫助？謝謝！

來源

2013-02-25 user2101463

幼稚的做法是檢查所有長度爲1..'len（l）'的所有可能子列表。也就是說，您需要檢查每個子列表長度1，然後檢查每個子列表長度2，然後檢查每個子列表長度3，並輸出找到的最大值。 – 2013-02-25 02:16:13

[Maximum sum sublist？]的可能重複（http://stackoverflow.com/questions/15062844/maximum-sum-sublist） – Dukeling 2014-06-13 06:35:18

我認爲這是一個家庭作業，所以我不會嘗試谷歌算法在這裏和/或張貼太多的代碼。

的一些想法（只是從我的頭頂，因爲我喜歡這些類型的任務:-)）

隨着用戶LC已經指出的天真，也詳盡的方法是測試每一個子表。我相信你的（user2101463）代碼會朝着這個方向發展。只需使用sum()來構建總和並與已知最好的比較。要使用合理的起始值來填充最好的已知總和，只需使用列表的第一個值即可。

the_list = [4,-2,-8,5,-2,7,7,2,-6,5] 

best_value = the_list[0] 
best_idx = (0,0) 
for start_element in range(0, len(the_list)+1): 
    for stop_element in range(start_element+1, len(the_list)+1): 
     sum_sublist = sum(the_list[start_element:stop_element]) 
     if sum_sublist > best_value: 
      best_value = sum_sublist 
      best_idx = (start_element, stop_element) 

print("sum(list([{}:{}])) yields the biggest sum of {}".format(best_idx[0], best_idx[1], best_value))

這當然有二次運行時O（N^2）。這意味着：如果由輸入列表的元素數量定義的問題大小隨N增長，則運行時隨N * N增長，並帶有一些任意係數。

一些技巧的改進：因爲他們降低實現的總和

如果遇到負數的序列

顯然負數並不好，重新啓動您的最佳子列表該序列後，如果總和到目前爲止的最佳列表加上負數是< 0.在您的示例列表中，前三個數字不能成爲最佳列表的一部分，因爲4的積極效果總是被-2, -8否定。
可能這甚至會導致一個O(N)的實現，它只是從頭到尾迭代，記住最有名的起始索引，同時計算從該起始索引開始的全部總和的運行總和以及最後一個連續序列的正和負小計正數和負數。
一旦這樣一個最好的列表中找到，這可能需要一個最終清理刪除尾隨負子列表諸如-6, 5在你的例子結束。

希望這會導致在正確的方向。

來源

2013-02-25 14:13:55 cfi

這被稱爲'最大子陣問題'，可以在線性時間內完成。 wikipedia article有你的答案。

來源

2013-03-13 07:51:16

最優化的解決方案是採用O（n）的線性運行時間。但此問題有「n * lgn」運行時解決方案（基於分而治之算法）和「n^2」運行時解決方案。如果您對這些算法感興趣，這裏是鏈接introduction to algorithms這是強烈推薦，在這裏我寫一個代碼java它有線性運行時間。

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    Scanner sc=new Scanner(System.in); 
    int n=sc.nextInt(); 
    int []A=new int[n]; 
    int highestsum=Integer.MIN_VALUE; 
    int sumvariable=0; 
    int x=0; 
    for(int i=0;i<n;i++) 
    { 
     A[i]=sc.nextInt(); 
    } 
    for(int i=0;i<n;i++) 
    { 
     sumvariable+=A[i]; 
     if(sumvariable<0) 
     { 
      if(sumvariable>=highestsum) 
      { 
       highestsum=A[i]; 
       sumvariable=A[i]; 
      } 
      else 
      { 
       sumvariable=0; 
      } 
     } 
     else 
     { 
      if(sumvariable>highestsum) 
      { 
       highestsum=sumvariable; 
      } 

     } 
    } 
    System.out.println(highestsum); 
}

來源

2016-07-04 12:29:15

返回最大子列表的總和

回答

相關問題