Найти наибольшую возможную разницу в массиве с меньшим целым числом, встречающимся ранее

Это вопрос интервью:

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

Constraint: Номера не уникальны. Диапазон - целочисленный диапазон java. (или любой другой язык)

Пример:

ввод 1: {1, 100, 2, 105, -10, 30, 100}

Самое большое различие между -10 и 100 → 110 (здесь -10 находится на 5-м индексе, а 100 - на 7-м индексе)

ввод 2: {1, 100, 2, 105, -10, 30, 80}

Самое большое различие между 1 и 105 → 104 (здесь 1 находится в первом индексе, а 105 - в 4-м индексе)

Возможное решение:

Один из подходов - проверка всех возможных различий и сохранение трека самой большой разницы, обнаруженной до сих пор сложностью O (n ^ 2).

можно ли это сделать лучше, чем время O (n ^ 2)?

Ответ 1

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

Кроме того, вы можете сохранить элемент, чтобы сохранить максимальную разницу и сразу дать результат. O (n), O (1) пространство.

int max = INT_MIN;
int maxdiff = 0;

for (i = sizeof(arr) / sizeof(int) - 1; i >= 0; i--) {
  if (max < arr[i]) {
    max = arr[i];
  }
  int diff = max - arr[i];
  if (maxdiff < diff) {
    maxdiff = diff;
  }
}

print maxdiff;

Ответ 2

Dhandeep algoritm хорош, и Vivek перевод кода на Java работает! Кроме того, мы можем также сканировать массив как обычно, а не наоборот:

int seed[] = {1, 100, 2, 105, -10, 30, 100};
int maxDiff=Integer.MIN_VALUE, minNumber = Integer.MAX_VALUE;

for (int i = 0; i < seed.length ; i++){
    if(minNumber > seed[i]) 
       minNumber = seed[i];

    maxDiff = Math.max(maxDiff, (seed[i]-minNumber));
}
System.out.println(maxDiff);

Ответ 3

Спасибо @Dhandeep Jain за ответ. Существует версия java:

//int seed[] = {1, 100, 2, 105, -10, 30, 100};
        int seed[] = {1, 100, 2, 105, -10, 30, 80};
        int maxDiff=Integer.MIN_VALUE, maxNumber = Integer.MIN_VALUE;

        for (int i = (seed.length-1); i >=0 ; i--){
            if(maxNumber < seed[i]) 
                maxNumber = seed[i];

            maxDiff = Math.max(maxDiff, (maxNumber - seed[i]));
        }
        System.out.println(maxDiff);

Ответ 4

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

Ответ 5

public class Test{

    public static void main(String[] args){

        int arr1[] = {1,2,5,7,9};
        int arr2[] = {20,25,26,35};
        int diff = 0;
        int max = 0;

        for(int i=0;i<arr1.length;i++){
            for(int j=0;j<arr2.length;j++){

                diff =  Math.abs(arr1[i]-arr2[j]);
                if(diff > max){
                    max = diff;
                }
            }
        }
    System.out.println(max);
    }   
}

Ответ 6

    // Solution Complexity : O(n)   
    int maxDiff(int a[], int n){
        //  Find difference of adjacent elements
        int diff[n+1];
        for (int i=0; i < n-1; i++)
            diff[i] = a[i+1] - a[i];

        // Now find the maximum sum sub array in diff array
        int max_diff = diff[0];
        for (int i = 1 ; i < n-1 ; i++ ) {
            if( diff[i-1] > 0 ) diff[i] += diff[i-1];
            if( max_diff < diff[i] ) max_diff = diff[i];
        }
        return max_diff;
    }

Ответ 7

Сначала найдите разницу между смежными элементами массива и сохраните все различия во вспомогательном массиве diff [] размера n-1. Теперь эти проблемы превращаются в поиск максимального субарама суммы этого разностного массива.

Ответ 8

Решение Ruby:

a = [3, 6, 8, 1, 5]
min = 10**6
max_diff = -10**6
a.each do |x|
  min = x if x < min
  diff = x - min
  max_diff = diff if diff > max_diff
end
puts max_diff

Ответ 9

public static void findDifference(Integer arr[]) {
    int indexStart = 0;
    int indexMin = 0;
    int indexEnd = 1;
    int min = arr[0];
    int diff = arr[1] - arr[0];
    for (int counter = 1; counter < arr.length; counter++) {
        if (arr[counter] - min > diff) {
            diff = arr[counter] - min;
            indexEnd = counter;
            indexStart = indexMin;
        }
        if (arr[counter] < min) {
            min = arr[counter];
            indexMin = counter;
        }
    }
    System.out.println("indexStart = " + indexStart);
    System.out.println("indexEnd = " + indexEnd);
    System.out.println("diff = " + diff);
}

Ответ 10

Я уверен, что это должно решить вашу проблему:

    int largestNumber = Integer.MIN_VALUE;
    int smallestNumber = Integer.MAX_VALUE; 

    for(int i = 0; i < yourArray.Length; i++)
    {
        if(yourArray[i] > largestNumber)
            largestNumber = yourArray[i];

        if(yourArray[i] < smallestNumber)
            smallestNumber = yourArray[i];

    }

    int biggestDifference = largestNumber - smallestNumber ;