从数组中获取最大子数
我最近在测试中遇到了这个问题，并且完全不了解问题所要求的内容，特别是基于以下示例：
max_subsum
编写一个方法max_subsum（numbers），它接受一个数组并返回具有最大总和的连续范围的起始和结束索引。
max_subsum（[100，-101,200，-3,1000]）== [2,4]
max_subsum（[1,2,3]）== [0,2]
提示：遍历所有子arrays; 计算每个子arrays的总和，并与目前为止看到的最大子数进行比较。 子arrays由其起始索引和结束索引定义，因此遍历所有索引对。 你应该使用两个循环，一个嵌套在另一个循环中。
我在示例中没有看到任何子arrays。 示例的输出仅显示数组中最小值和最大值的索引。 如果这就是问题所要求的，那么子arrays的总和正在发生。 我必须遗漏一些简单的东西，我只是不知道那是什么。 别人看到了吗？
这些是第一个数组的子数组及其总和：
[100].inject(:+) #=> 100 [100, -101].inject(:+) #=> -1 [100, -101, 200].inject(:+) #=> 199 [100, -101, 200, -3].inject(:+) #=> 196 [100, -101, 200, -3, 1000].inject(:+) #=> 1196 [-101].inject(:+) #=> -101 [-101, 200].inject(:+) #=> 99 [-101, 200, -3].inject(:+) #=> 96 [-101, 200, -3, 1000].inject(:+) #=> 1096 [200, -3, 1000].inject(:+) #=> 1197 [-3, 1000].inject(:+) #=> 997 [1000].inject(:+) #=> 1000
[200, -3, 1000]具有最大的总和
这是我对你的问题的快速解决方案=）
拆分电话以了解我在做什么=）
def max_subsum(a) (0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } }.inject([a[0], 0..0]) { |max, i| a[i].inject(:+) > max.first ? [a[i].inject(:+),i ]: max }.last end
输出：
max_subsum([100, -101, 200, -3, 1000]) => 2..4 max_subsum([1, 2, 3]) => 0..2
你可以转换为数组..我没有打扰因为我喜欢范围=）
针对这个问题的动态编程解决方案会更有效率，但我认为你应该提供与我在考试期间所做的一样的事情:-)
说明：
(0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } }
返回给我数组中所有可能的连续位置。 您可以将此视为嵌套循环。
然后我注入值[a[0], 0..0]并假设它是解决方案： a[0]是最大值， 0..0是开始到结束索引。 在注入内部，我将最大值与flat_map中数组当前切片的总和进行比较，如果它更大，我返回切片和最大值。
卡丹的算法就是你想要的。 在这篇博客中你也可以找到很好的参考资料。