Если я правильно понимаю вашу проблему, вы ищете два индекса (i, j) в массиве с i ‹ j, который имеет наибольшее отношение A[j]/A[i]. Если это так, вы можете уменьшить это до этой связанной проблемы< /strong>, который просит вас найти индексы (i, j) с ij таким образом, чтобы A[j] - A[i] было как можно больше. Эта задача имеет очень быстрый O(n)-временной и O(1)-пространственный алгоритм, который также можно адаптировать к этой задаче. Интуиция состоит в том, чтобы решить задачу для массива, состоящего только из первого элемента вашего массива, затем для первых двух элементов, затем для первых трех и т. д. Как только вы решили задачу для первых n элементов массива, у вас есть общее решение проблемы.
Давайте подумаем, как это сделать. Первоначально, когда вы рассматриваете только первый элемент массива, лучшее процентное увеличение, которое вы можете получить, составляет 0%, сравнивая элемент с самим собой. Теперь предположим (индуктивно), что вы решили задачу для первых k элементов массива и хотите посмотреть, что произойдет, когда вы посмотрите на следующий элемент массива. Когда это происходит, выполняется одно из двух условий. Во-первых, максимальное процентное увеличение первых k элементов также может быть максимальным процентным увеличением первых (k + 1) элементов. Например, если (k+1)st элемент массива является очень маленьким числом, то, скорее всего, вы не сможете получить большое процентное увеличение от чего-то в первых 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 мин 3 1 1 1 1 лучший (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 [i]) максимизируется. Поскольку логарифмическая функция монотонно возрастает, это означает, что вы нашли пару значений, где A[j] / A[i] максимальны, как и предполагалось.
person
templatetypedef
schedule
30.08.2011
finalValue/initialValue? - person Nikita Rybak schedule 05.02.2011O(n), если разрешите пространственную сложностьO(n)- person Foo Bah schedule 05.02.2011