Сегодня рассмотрим максимальную разность в массиве
задача
найти максимальную разность в массиве array[j] — array[i], где j>i
мы можем решить эту задачу с помощью
- O(n2) 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(n2)
Рассмотрим другой метод
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(n2)