返回最大子列表的总和

我必须编写一个函数，它接受一个整数列表并返回列表的最大总和子列表。一个例子是：返回最大子列表的总和

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

返回最大子列表的总和

回答

相关问题