найти максимально возможную разницу между a [i] и a [j], где 0 <i <a.length и i <j <a.length

Question

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

Учитывая:Массив целых чисел представляет цену акции предмета. Задача: найти максимально возможную выгоду, если мы на одну акцию в день X, и продать ее в день X + n.

Я написал функцию, которая:

1. предполагает, что maxPossibleBenefit можно выполнить в день 2:

1.1 maxPossibleBenefit = a [1] - a [0]

проходит через массив от [0] до [a.length -1]:

2.1. Если a [X + n] - a [X]> maxPossibleBenefit, то maxPossibleBenefit =a [X + n] - a [X].

3. Когда X + n == a.length (мы достигаем конца массива), повторите шаги 2 и 2.1, начиная с [1],затем из [2], пока мы не достигнем a. [length-2], чтобы сравнить последние 2 элемента.

public static int maxBenefit(int[] arr) {

        //first, assuming that max benefit can be received on day 2
        int maxBenefit = arr[1] - arr[0];
        // traverse the entire array and check,
        // will we get more benefit if we buy on day one
        // and sell on day 2, 3, up until the last day in the range:
        for (int i = 0; i < arr.length - 1; i++) {
            // with every run we shift purchase date by one into the future
            for (int j = i; j < arr.length - 1; j++) {
                // if we sell later than on day 2, will we get more benefit?
                if ((arr[j + 1] - arr[j]) > maxBenefit)
                    maxBenefit = arr[j + 1] - arr[j];
            }
        }
        return maxBenefit;
    }

Но с массивом {8, 6, 5, 6, 7, 9, 10,7, 9, 4}, функция возвращает 2, а должно быть 5 (a [6] - a [2]).

Не могли бы вы помочь мне найти ошибку в моем алгоритме?

Answer 1

Вы неправильно используете i и j и не рассчитываете разницу между ними.

public static int maxBenefit(int[] arr) {

    //first, assuming that max benefit can be received on day 2
    int maxBenefit = arr[1] - arr[0];
    // traverse the entire array and check,
    // will we get more benefit if we buy on day one
    // and sell on day 2, 3, up until the last day in the range:
    for (int i = 0; i < arr.length - 1; ++i) {
        // with every run we shift purchase date by one into the future
        for (int j = i + 1; j < arr.length; ++j) {
            // if we sell later than on day 2, will we get more benefit?
            int benefit = arr[j] - arr[i];
            if ( benefit > maxBenefit)
                maxBenefit = benefit;
        }
    }
    return maxBenefit;
}