mail@pastecode.io avatarunknown
10 days ago
2.3 kB
"""The following code solves the problem of finding the maximum difference between two elements chosen from
distinct arrays from a list of N arrays of at most M elements each
If the two chosen elements could be from the same array, then we would just choose the minimum and the maximum
among all the elements, no matter the array they belong to
But by using this strategy, we can have the case where both min and max are from the same array, which is not
allowed in this problem. To counter that, we move to the couple with the second greatest difference, which is
either the first maximum with the second minimum or the second maximum with the first minimum, we take
the one with the greatest difference
With the example below, minimums (min of each arraay) are [-4, -2, 1, -1, -2] and 
maximums (max of each array) are [10, 8, 9, 8, 8]
If we take the minimum of minimums and the maximum of maximums, we find -4 and 10, with a difference of 14, the
greatest possible difference. But they belong to the same array (the array 0)
The second minimum is -2 and the second maximum is 9, so we take either the first maximum with the second
minimum (10 and -2), with a difference of 12, or the second maximum with the first minimum (9 and -4),
with a difference of 13. We choose the second one because it has a higher difference.
So the greatest difference we can get by choosing elements from distinct arrays is 13"""

def max_diff(arrays):
    mins = [min(arr) for arr in arrays]
    maxs = [max(arr) for arr in arrays]

    min_of_mins = min(mins)
    min_of_mins_index = mins.index(min_of_mins)
    second_min_of_mins = min(mins[:min_of_mins_index] + mins[min_of_mins_index+1:])

    max_of_maxs = max(maxs)
    max_of_maxs_index = maxs.index(max_of_maxs)
    second_max_of_maxs = max(maxs[:max_of_maxs_index] + maxs[max_of_maxs_index+1:])

    if min_of_mins_index != max_of_maxs_index:
        return max_of_maxs - min_of_mins
        return max(second_max_of_maxs-min_of_mins, max_of_maxs-second_min_of_mins)
arrays = [
    [-4, 5, 3, 2, 10],
    [8, -2, 6, 1],
    [7, 9, 3, 1, 4],
    [1, 8, -1, 6, 5, 3],
    [5, -2, 6, 3, 0, 8, 4, 7]

# Output: 13 (it took -4 from the first array and 9 for the third array, and the difference is 13)