Get the most out of your array

Question

I had this question in the test recently and I don’t understand what it is about, especially based on examples:

max_subsum

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

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

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

Tips: iterate through all subarrays; calculate the sum of each subarray and compare with max. the house seen so far. A subarray is determined by its start index and end indices, so we iterate over all pairs of indices. You should probably use two loops, one nested inside the other.

I do not see any subarrays in the examples. The result from the examples simply shows the indices of the smallest and largest values ​​in the array. If this is what the question asks for, then what sums the subarrays. I have to miss something simple, I just don’t know what it is. Does anyone else see this?

Answer 1

These are the first subarrays of the array along with their sums:

[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] has the largest amount

Answer 2

Here is my quick solution to your problem =)

Separate the challenges 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

Output:

max_subsum([100, -101, 200, -3, 1000])
=> 2..4
max_subsum([1, 2, 3])
=> 0..2

You can convert to an array. I was not worried since I like the range =)

, , - , : -)

:

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

. .

[a[0], 0..0] , : a[0] , 0..0 . max flat_map, , max.

Answer 3

- , . .

Answer 4

static int[] maxSubSum(int[] arr) {
    int start = 0;
    int end = 0;
    int thisSum = arr[0];
    int maxSum = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (thisSum > 0) {
            thisSum += arr[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
                end = i;
            }
        } else {
            thisSum = arr[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
                start = i;
                end = i;
            }
        }
    }
    return new int[]{start, end, maxSum};
}

}