从阵列中获得最大的个子求和 [英] Get max subsum from an array

问题描述

最近，我在测试这个问题，并在所有不明白的问题是要求，特别是基于实例：

I had this question on a test recently and don't understand at all what the question is asking for, especially based on the examples:

max_subsum

写一个方法，max_subsum（数字），这需要一个数组并返回
  它具有连续范围的开始和结束的索引
  最大的一笔。

Write a method, max_subsum(numbers), which takes an array and returns the start and end indices of the consecutive range which has the largest sum.

max_subsum（[100，-101，200，-3，1000]）== [2,4]

max_subsum([100, -101, 200, -3, 1000]) == [2, 4]

max_subsum（[1，2，3]）== [0,2]

max_subsum([1, 2, 3]) == [0, 2]

提示：在所有的子阵迭代;计算每个的总和
  子阵，并比较迄今所看到的最大个子求和。一个子阵列
  其开始索引和结束索引定义，因此通过所有迭代
  对指数的。你应该使用两个循环，一是内部嵌套
  其他。

Hints: iterate through all the subarrays; compute the sum of each subarray and compare to the max subsum seen so far. A subarray is defined by its start index and end indices, so iterate through all pairs of indices. You should probably use two loops, one nested inside the other.

我没有看到任何的例子子阵列。从实施例的输出简单地示出了阵列中最小和最大的值的索引。如果这就是问题的要求，那么什么求和子阵中正在发生的事情。我必须失去了简单的东西，我只是不知道那是什么。难道别人看呢？

I don't see any subarrays in the examples. The output from the examples simply shows the indices of smallest and largest values in the array. If that's what the question is asking for, then what summation of subarrays is happening. I must be missing something simple, I just don't know what that is. Does someone else see it?

推荐答案

下面是我的快速解决您的问题=）

Here's my quick solution to your problem =)

拆分电话，以了解我在做什么=）

Split the calls in order to understand what I'm doing =)

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

您可以转换成数组..我没有理会，因为我喜欢的范围=）

You can convert to array.. I did not bother as I like the range =)

一个动态规划解决这个问题的效率会比较高，但我认为你预计可提供沿着什么，我考试时的做东西线： - ）

A dynamic programming solution to this problem would be more efficient but I think you are expected to provide something along the lines of what I did during an exam :-)

说明：

(0...a.length).flat_map { |i| (i...a.length).map { |j| i..j } }

返回到我所有阵列中的可能的连续的位置。你可以考虑您的嵌套的循环。

returns to me all the possible consecutive positions in the array. You can consider this your nested loops.

我再注入值 [A [0]，0..0] 并假设它的解决方案： A [0] 作为最大值和 0..0 作为开始到结束索引。内注射，我比较最大值从flat_map阵列的当前片的总和，如果是大的，我返回切片和最大

I'm then injecting the value [a[0], 0..0] and assuming it's the solution: a[0] being the max value and 0..0 being the start to end index. Inside inject, I'm comparing the max to the sum of the current slice of the array from flat_map, if it's bigger, I return the slice and the max.

这篇关于从阵列中获得最大的个子求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！