Максимальная абсолютная разница сумм значений и индексов четырех массивов

Вам даны четыре массива A, B, C, D размером N каждый.
Найдите максимальное значение (M) приведенного ниже выражения

M = max(|A[i] - A[j]| + |B[i] - B[j]| + |C[i] - C[j]| + |D[i] - D[j]| + |i -j|)
Where 1 <= i < j  <= N <br />

а здесь |x| относится к абсолютному значению x.

Ограничения

2 <= N <= 10^5  
1 <= Ai,Bi,Ci,Di <= 10^9
  • Ввод: Н,А,Б,С,Г
  • Выход: М

Ex.- 

Input-   
5  
5,7,6,3,9  
7,9,2,7,5  
1,9,9,3,3  
8,4,1,10,5

Выход-

24

Изображение вопроса

я пробовал так

def max_value(arr1,arr2,arr3,arr4, n): 
    res = 0; 
    # Iterating two for loop,  
    # one for i and another for j. 
    for i in range(n): 
        for j in range(n):  
            temp= abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(arr3[i] - arr3[j]) + abs(arr4[i] - arr4[j]) + abs(i - j)
            if res>temp:
                res = res
            else:
                res = temp
    return res;

Это О(n^2). Но я хочу лучшее решение временной сложности. Это не будет работать для более высоких значений N.

Вот решение для одного массива


python arrays absolute algorithm difference
person sks    schedule 31.05.2020    source источник
comment
В вашем коде i идет от 1 до n, а j идет от 1 до n, но в первом утверждении вы говорите, что i всегда меньше, чем j. Я предполагаю, что оба идут?   -  person Znerual    schedule 31.05.2020

Ответы (2)


arrow_upward
4
arrow_downward

Можно обобщить решение для одного массива, которое вы показали. Учитывая число массивов K, включая массив индексов, можно сделать 2**K возможных комбинаций массивов, чтобы избавиться от абсолютных значений. Тогда легко просто взять максимум и минимум каждой из этих комбинаций отдельно и сравнить их. Это порядок O (Kn * 2 ^ K), намного лучше, чем исходный O (Kn ^ 2) для значений, которые вы сообщаете.

Вот код, который работает с произвольным количеством входных массивов.

import numpy as np

def run(n, *args):
    aux = np.arange(n)

    K = len(args) + 1
    rows = 2 ** K
    x = np.zeros((rows, n))
    for i in range(rows):
        temp = 0
        for m, a in enumerate(args):
            temp += np.array(a) * ((-1) ** int(f"{i:0{K}b}"[-(1+m)]))
        temp += aux * ((-1) ** int(f"{i:0{K}b}"[-K]))
        x[i] = temp

    x_max = np.max(x, axis=-1)
    x_min = np.min(x, axis=-1)
    res = np.max(x_max - x_min)
    return res

Цикл for, возможно, заслуживает более подробного объяснения: чтобы составить все возможные комбинации абсолютных значений, я присваиваю каждой комбинации целое число и полагаюсь на двоичное представление этого целого числа, чтобы выбрать, какие из K векторов следует считать отрицательными.

person Gianluca Micchi    schedule 31.05.2020
comment
Не уверен, есть ли у вас ошибка "один за другим", но run(5, (5,7,6,3,9), (7,9,2,7,5), (1,9,9,3,3), (8,4,1,10,5)) дает 24 вместо 25. (Или вопрос имеет неправильный ожидаемый результат.) - person aneroid; 31.05.2020
comment
Используя код OP, ответ также 24 для значений i=2, j=3. Я думаю, что это опечатка в вопросе. - person Gianluca Micchi; 31.05.2020
comment
Да, это 24, а не 25. Спасибо. - person sks; 31.05.2020

arrow_upward
0
arrow_downward

Идея для более быстрого решения

  • Если вас интересует только максимум M, вы можете искать минимальное и максимальное значение A, B, C, D и i-j. Допустим, i_Amax - это индекс i для максимума A.
  • Теперь вы находите значение B[i_Amax], C[i_Amax].... и то же самое для i_Amin и вычисляете M с разницей максимального и минимального значений.
  • Вы повторили предыдущий шаг с индексом для максимального значения B, поэтому i_Bmax и вычислите M, вы повторяете, пока не пройдете через A, B, C, D и i-j
  • Теперь у вас должно быть пять терминов, и один из них должен быть максимальным.

Если у вас нет четкого минимума или максимума, вы должны вычислить индексы для всех возможных минимумов и максимумов.

Я думаю, что он должен найти любой максимум и быстрее, чем n ^ 2, особенно для больших n, но я сам его не реализовал, поэтому вам нужно подумать, чтобы проверить, не сделал ли я логическую ошибку, и нельзя найти каждый максимум с этой идеей.

Надеюсь, это поможет!

person Znerual    schedule 31.05.2020