Максимальная абсолютная разница в массиве

Я столкнулся с этим вопросом алгоритма. Я смог реализовать решение O (n ^ 2). Есть ли лучший способ сделать это в O (n) времени?

Вопрос:

Вам задан массив из N целых чисел, A1, A2 ,…, AN. Вернуть максимальное значение f(i, j) для всех 1 ≤ i, j ≤ N. f(i, j) определяется как |A[i] - A[j]| + |i - j|, где |x| обозначает абсолютное значение x.

Пример:

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

Итак, вернем 5.

Мой ответ:

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int maxSum = 0;

        for(int i=1; i<=A.size()-1; i++){
            for(int j=i+1; j<=A.size(); j++){
                int tempSum = sum(A.get(i-1), A.get(j-1), i, j);

                if(tempSum > maxSum) {
                    maxSum = tempSum;
                }
            }
        }

        return maxSum;
    }

    public int sum(int Ai, int Aj, int i, int j) {
        return Math.abs(Ai-Aj) + Math.abs(i-j);
    }
}

Также в моем решении внутренний цикл работает от я + 1 до N, поэтому наихудший случай - N-1 для этого цикла. Мое общее решение все еще O (n ^ 2)?

Ответы

Ответ 1

Да, ваше решение по-прежнему O(N^2) как (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.

Я покажу, как решить более общую задачу в линейном времени: дать список точек в 2D-пространстве (x [i], y [i]), найти две самые далекие точки (относительно Манхэттенского расстояния).

Найдем следующие моменты: max (x [i] + y [i]), max (-x [i] + y [i]), max (-y [i] + x [i ]) и max (-x [i] - y [i]) среди всех i.
Позвольте вычислить расстояние между каждой точкой в списке и четырьмя точками, выбранными на предыдущем шаге, и выбрать самый большой. Этот алгоритм явно работает в линейном времени, так как он рассматривает пары точек t22. Я утверждаю, что это правильно.
Почему? Пусть исправить точку (x [k], y [k]) и попытаться найти от нее самую дальнюю. Рассмотрим произвольную точку (x [i], y [i]). Пусть расширяется абсолютное значение различий между их координатами. Предположим, что оно x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i]. Первый член - константа. Если x[i] + y[i] не является максимальным среди всех i, (x[i], y[i]) не может быть самым дальним. Три других случая (в зависимости от знака x [i] и y [i] в разложении) обрабатываются одинаково.

Ответ 2

Как описано Краскевич, я применил тот же алгоритм. Сложность кода O (4 * n) + O (4 * n), что делает общую сложность O (n).

Вот код.

int Solution::maxArr(vector<int> &A) {
int n=A.size(),max1=INT_MIN,max2=INT_MIN,max3=INT_MIN,max4=INT_MIN,ans=INT_MIN;
for(int i=0;i<n;i++){
    max1=max(max1,A[i]+i);
    max2=max(max2,-A[i]+i);
    max3=max(max3,A[i]-i);
    max4=max(max4,-A[i]-i);
}
for(int i=0;i<n;i++){
    ans=max(ans,max1-A[i]-i);
    ans=max(ans,max2+A[i]-i);
    ans=max(ans,max3-A[i]+i);
    ans=max(ans,max4+A[i]+i);
}
return ans;
}

Ответ 3

public int maxArr(ArrayList<Integer> A) 
{    
  int n=A.size(),max1=A.get(0),max2=A.get(0),int min1=A.get(0),min2=A.get(0),ans=0;

  for(int i=0;i<n; i++){
    max1=max(max1, A.get(i)+i);
    max2=max(max2, A.get(i)-i);
    min1=min(min1,  A.get(i)+i);
    min2=min(min2, A.get(i)-i);
  }

   ans = max(ans, (max2 - min2));
   ans = max(ans, (max1 - min1));

   return ans;
}

Здесь

int max1 = INT_MIN, max2 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;

Ответ 4

Это java-решение вашей проблемы.

public class Solution {
public int maxArr(ArrayList<Integer> A) {
    if(A.size() < 2) return 0;
    int res =Integer.MIN_VALUE;
    int max1=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,min1 = Integer.MAX_VALUE,min2=Integer.MAX_VALUE;
    for(int i =0; i < A.size(); ++i){
        max1 = Math.max(A.get(i) + i, max1);
        min1 = Math.min(A.get(i) + i, min1);

        max2 = Math.max(A.get(i) - i, max2);
        min2 = Math.min(A.get(i) - i, min2);
    }

    res = Math.max(max1-min1, res);
    res = Math.max(max2-min2, res);
    return res;
  }                    
}

Ответ 5

Мы можем, конечно, использовать некоторую математику здесь. Попытайтесь расширить функцию, которую вы пытаетесь максимизировать. F (i, j) = | A [i] - A [j] | + | я - j | Развернув его, мы получим 4 значения F.

A [i] - A [j] + я - j равно [A [i] + i] - [A [j] + j]
-A [i] + A [j] + я - j равно [-A [i] + i] - [-A [j] + j]
A [i] - A [j] + j - я равно [A [i] - i] - [A [j] -j]
-A [i] + A [j] + j - я равно [-A [i] - i] - [-A [j] -j]

Вычислить максимальное и минимальное значение [A [i] + i], [- A [i] + i], [A [i] - i], [- A [i] - i] для всех элементов в векторе/массиве. назовите его max1, max2, max3, max4 и min1, min2, min3, min4.

Ваш ответ - Макс ((max1-min1), (max2-min2), (max3-min3), (max4-min4)).

Вот ссылка на проблему, если кому-то интересно: - Ссылка на проблему

Ниже моя реализация в С++

int Solution::maxArr(vector<int> &A) {
int max1 = INT_MIN,max2 = INT_MIN,max3 = INT_MIN,max4 = INT_MIN,ans = INT_MIN;
int min1 = INT_MAX,min2 = INT_MAX,min3 = INT_MAX,min4 = INT_MAX;
for(int i=0;i<A.size();i++){
    max1 = max(max1,A[i] + i);
    max2 = max(max2,A[i] - i);
    max3 = max(max3,-A[i]+i);
    max4 = max(max4,-A[i]-i);

    min1 = min(min1,A[i] + i);
    min2 = min(min2,A[i] - i);
    min3 = min(min3,-A[i]+i);
    min4 = min(min4,-A[i]-i);

}


    ans = max(ans,max1 - min1);
    ans = max(ans,max2 - min2);
    ans = max(ans,max3 - min3);
    ans = max(ans,max4 - min4);

return ans;

}

Ответ 6

f(i, j) = |A[i] - A[j]| + |i - j| можно упростить следующими способами (на основе определения abs()):

a) (A[j]-j)-(A[i]-i)
b) (A[j]+j)-(A[i]+i)
c) (A[i]+i)-(A[j]+j)
d) (A[i]-i)-(A[j]-j)

for 0< i,j < N - a и d аналогичны, а также b и c. Поэтому, если мы можем вычислить массив A[i]-i и A[i]+i и найти максимальную разницу внутри него, мы получим ответ.

  public class Solution {
        public int maxArr(ArrayList<Integer> A) {
            int n = A.size();
            int max = 0;
            int []a = new int [n];
            int []b = new int [n];
            for(int i=0;i<n;i++){
                a[i]=A.get(i)-i;
                b[i]=A.get(i)+i;
            }
            Arrays.sort(a);
            Arrays.sort(b);
            max = Math.max(a[n-1]-a[0], b[n-1]-b[0]);
            return max;
        }
    }

Ответ 7

Ссылка на реализацию

int Solution::maxArr(vector<int> &A) {
    int max1 , max2 , min1 , min2;
    max1 = max2 = INT_MIN;
    min1 = min2 = INT_MAX;
    int N = A.size();
    for(int i=0;i<N;i++){
        max1 = max(max1,A[i]+i);
        max2 = max(max2,A[i]-i);
        min1 = min(min1,A[i]+i);
        min2 = min(min2,A[i]-i);
    }
    int ans = 0;
    ans = max(ans,max1-min1);
    ans = max(ans,max2-min2);
    return ans;
}