Наибольший процент увеличения

Question

Допустим, у нас есть следующий набор чисел, представляющих значения во времени

1 2 3 10 1 20 40 60

Сейчас я ищу алгоритм, чтобы найти самый высокий процент увеличения от одного раза к другому. В приведенном выше случае ответом будет пара (1, 60), которая увеличится на 6000%.

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

1-я итерация:

1-2 1-3 1-10 .. 1-60

2-я итерация

 2-3 2-10 2-1 ... 2-60

(и т.д.).

Это имеет сложность O (n ³ ).

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

У вас, ребята, есть какая-нибудь другая идея? Пожалуйста, поправьте меня, если мои идеи не верны!

Answer 1

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

while true:
    indexOfMax = max(list)
    indexOfMin = min(list)
    list.remove(indexOfMax)
    list.remove(indexOfMin)
    if(indexOfmax < indexOfMin)
        contine
    else if(indexOfMax == indexOfMin)
        return -1
    else
        SUCCESS

Answer 2

Если я правильно понимаю вашу проблему, вы ищете два индекса (i, j) в массиве с i этой связанной проблемы , которая просит вас найти индексы (i, j) с i ≤ j, такие что A [j] - A [я] как можно больше.Эта проблема имеет очень быстрый O (n) -время, O (1) -пространственный алгоритм, который также может быть адаптирован к этой проблеме.Интуиция состоит в том, чтобы решить проблему для массива, состоящего только из первого элемента вашего массива, затем для первых двух элементов, затем из первых трех и т. Д. Как только вы решили проблему для первых n элементов массива,у вас есть общее решение проблемы.

Давайте подумаем, как это сделать.Первоначально, когда вы рассматриваете только первый элемент массива, лучший процент увеличения, который вы можете получить, составляет 0%, если сравнивать элемент с самим собой.Теперь предположим (индуктивно), что вы решили проблему для первых k элементов массива и хотите посмотреть, что произойдет, если вы посмотрите на следующий элемент массива.Когда это происходит, выполняется одно из двух условий.Во-первых, максимальное процентное увеличение по первым k элементам также может быть максимальным процентным увеличением по первым (k + 1) элементам.Например, если (k + 1) -й элемент массива является чрезвычайно малым числом, то, скорее всего, вы не сможете получить значительный процентный рост от чего-то в первых k элементах до этого значения.Во-вторых, максимальное процентное увеличение может быть от одного из первых k элементов до (k + 1) -го элемента.Если это так, то наибольшее процентное увеличение будет от наименьшего из первых k элементов к (k + 1) -ому элементу.

Объединяя эти два случая, мы получаем, что наилучший процентный рост по сравнению спервые k + 1 элементов - это максимум

• Наибольший процент увеличения первых k элементов или
• Процент увеличения от наименьшего из первых k элементов к (k+ 1) первый элемент.

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

1  2  3  10  1  20  40  60

алгоритм будет работать так:

       1       2       3       10        1       20       40        60
min        1       1        1       1       1         1        1        1
best     (1,1)   (1, 2)  (1, 3)  (1, 10)  (1, 10)  (1, 20)   (1, 40)  (1, 60)

, и вы выведите (1, 60) как наибольший процент увеличения,В другом массиве, таком как этот:

3   1   4   2   5

, алгоритм будет выглядеть следующим образом: 3 1 4 2 5 min 3 1 1 1 1 best (3,3) (3,3) (1,4) (1,4) (1,5)

и вы получите (1, 5).

Весь этот алгоритм использует только O (1) пробел и работает вO (n) время, которое является чрезвычайно хорошим решением проблемы.

В качестве альтернативы, вы можете подумать о том, чтобы свести эту проблему непосредственно к проблеме максимальной прибыли от одной продажи, взяв логарифм всех значений вваш массив.В этом случае, если вы найдете пару значений, где log A [j] - log A [i] максимизировано, это эквивалентно (с использованием свойств логарифмов) нахождению пары значений, где log (A [j] / A[я]) максимизируется.Поскольку функция log монотонно увеличивается, это означает, что вы нашли пару значений, где A [j] / A [i] максимизируется, как и предполагалось.

Answer 3

То есть вы просто хотите сравнить каждое число попарно и посмотреть, какая пара имеет наибольшее отношение от второго числа к первому? Простая итерация с двумя циклами (один с i = 0 до n, а внутренний цикл с j = i + 1 до n) даст вам O (n ^ 2). Я предполагаю, что это на самом деле ваше оригинальное решение, но вы неправильно сказали, что сложность была O (n ^ 3). Это п ^ 2.

Вы можете добраться до O (n log n). Возьмите свой список, превратите его в список, где каждый элемент представляет собой пару (индекс, значение). Затем отсортируйте его по второму элементу пары. Затем добавьте два указателя в список, один идет слева (от 0 до n-1), а другой справа (от n-1 до 0). Найдите первую пару элементов таким образом, чтобы исходный индекс левого элемента был меньше исходного индекса правого элемента. Готово.

1 2 3 10 1 20 40 60
becomes
(1,0) (2,1) (3,2) (10,3) (1, 4) (20, 5) (40, 6) (60,7)
becomes
(1,0) (1,4) (2,1) (3,2) (10,3) (20,5) (40,6) (60,7)

Таким образом, ваш ответ 60/1, от индекса 0 до индекса 7.

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

Answer 4

Как я понимаю (вы не исправили меня в своем комментарии), вы хотите максимизировать a[i]/a[j] для всех j <= i. Если это правильно, то для каждого i нам нужно знать только наименьшее значение перед ним.

int current_min = INFINITY;
double max_increase = 0;
for (int i = 0; i < n; ++i) {
    current_min = min(current_min, a[i]);
    max_increase = max(max_increase, a[i] / min);
}