Максимальная разница в массиве

Сегодня рассмотрим максимальную разность в массиве
задача

найти максимальную разность в массиве array[j] — array[i], где j>i

мы можем решить эту задачу с помощью

1. O(n²) 2 для метода цикла
2. O(n) эффективное решение

Давайте рассмотрим первый вариант

int maxDif(int[] arr) {
    int maxDif = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] - arr[i] > maxDif) {
          maxDif = arr[j] - arr[i];
        }
      }
    }
    return maxDif;
  }

создадим переменную maxDif и инициализируем ее значением

Далее мы будем итерировать массив с помощью цикла for (i loop).
внутри этого цикла i мы будем перебирать все элементы, находящиеся в правой части, только по условию j>i мы начнем цикл j с i+1, для каждого элемента мы найдем разницу и если разница больше maxDif, то присвоим ей это значение.

Временная сложность:- O(n²)

Рассмотрим другой метод

int maxDifEfficient(int[] arr) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length - 1; i++) {
      max = Math.max(max, arr[i + 1]); 
      min = Math.min(min, arr[i]);
    }
    return max - min;
  }

логика этого метода заключается в том, что максимальная разница возможна, если мы вычтем между наибольшим и наименьшим числом
поэтому нам нужно найти наибольшее и наименьшее число в массиве с условием j>i
Здесь мы пытаемся решить задачу за O(n), для чего используем переменные min и max со значениями Integer.MAX_VALUE, Integer.MIN_VALUE соответственно
итерациями по массиву находим максимальное и минимальное значение

находим max с помощью Math.max(max,arr[i+1]); здесь j — это i+1, так как i+1 больше i, мы удовлетворяем условию j>i

и находим минимальное значение с помощью Math.min(min,arr[i]).

после завершения цикла мы получим наибольшее и наименьшее число в массиве с учетом условия j>i и можем вычесть их, чтобы найти максимальную разницу.

Временная сложность:- O(n²)