# Untitled

unknown

python

a year ago

2.3 kB

10

Indexable

Never

^{}

"""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 else: 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] ] print(max_diff(arrays)) # Output: 13 (it took -4 from the first array and 9 for the third array, and the difference is 13)