Покупка и продажа акций с O( n log n) сложностью по времени
РЕДАКТИРОВАТЬ:
Я ценю помощь от вас обоих, но я должен придерживаться границы O( n log n) временной полноты и должен использовать технику "разделяй и властвуй" с двоичной рекурсией. Я не очень ясно изложил это в первоначальной публикации
У меня есть несортированный массив целых, где я должен купить акции в i-й день и продать их в j-й день для максимальной прибыли, когда i-й (меньшее значение) день должен предшествовать j-му (большее значение) дню. До сих пор я нашел решение, которое возвращает дни покупки и продажи (значения индекса массива) и максимальную прибыль, но оно имеет сложность времени O(n^2), и мне трудно добраться до O (n войти n) время сложность и реализация разделяй и властвуй
public static Profit BestProfit( int[] a, int i, int j )
{
Profit bestProfit = new Profit();
int n = j;
int maxProfit = 0;
for(i = 0; i < n; i++)
{
for(j = i; j < n; j++)
{
if(a[j] - a[i] > maxProfit)
{
maxProfit = a[j] - a[i];
bestProfit.setBuy( i );
bestProfit.setSell( j );
bestProfit.setMaxProfit( maxProfit );
}
}
return bestProfit;
}
Параметры i - это начало массива, а j - в конце массива. Класс Profit - это класс, который я создал для хранения значений покупки, продажи и прибыли.
Я обнаружил, что мне нужно учесть три случая: наибольшая прибыль для первой половины массива, наибольшая прибыль для второй половины массива и случай, когда наименьшее значение находится в 1-й половине массива. и наибольшее значение находится во 2-й половине массива (я уже завершил эту часть проблемы с помощью простой функции min/max, которая решает окончательный вариант).
Я застрял, и любая помощь с реализацией разделяй и властвуй или советы хитрости будет принята с благодарностью!
3 ответа
В O(n) довольно просто:
public static Profit bestProfit(int[] a, int begin, int end) {
Profit bestProfit = new Profit();
int min = a[begin];
int max = a[begin];
int index = begin;
int buy = 0;
int sell = 0;
int minIndex = begin;
int maxIndex;
int maxProfit = 0;
for (int i = begin; i < end; i++) {
int n = a[i];
if (n < min) {
minIndex = index;
min = n;
max = n;
} else if (max < n) {
max = n;
maxIndex = index;
if (maxProfit < (max - min)) {
maxProfit = max - min;
buy = minIndex;
sell = maxIndex;
}
}
index++;
}
bestProfit.setBuy(buy);
bestProfit.setSell(sell);
bestProfit.setMaxProfit(maxProfit);
return bestProfit;
}
ИЗДАНО: разделяй и властвуй
public static int divideAndConquer(int[] a, int i, int j, Profit profit, int min) {
int minResult;
if (i+1 >= j) {
minResult = Math.min(a[i], min);
if (a[i] - min > profit.getMaxProfit()) {
profit.setBuy(min);
profit.setSell(a[i]);
profit.setMaxProfit(a[i] - min);
}
} else {
int n = (j+i)/2;
minResult = divideAndConquer(a, i, n, profit, min);
minResult = divideAndConquer(a, n, j, profit, minResult);
}
return minResult;
}
public static void main(String[] args) {
int[] prices = {20, 31, 5, 7, 3, 4, 5, 6, 4, 0, 8, 7, 7, 4, 1,10};
Profit profit =new Profit();
divideAndConquer(prices, 0, prices.length, profit, Integer.MAX_VALUE);
System.out.println(profit);
}
Ну, так как вы выражаете необходимость использовать разделяй и властвуй, я дам другой ответ.
Предположим, что цена акции определена в массиве: [p0, p1, ..., pn].
Мы можем разделить эту проблему на подзадачи в этом определении.
max profit = max(maxprofit([p0], [p1..pn]), maxprofit([p0..p1], [p2..pn]), ..., maxprofit([p0..pn-1], [pn]))
Первый аргумент для maxprofit - это массив цен покупки, а второй - массив цен продажи.
Посмотрите на первую подзадачу
maxprofit([p0], [p1..pn])
Мы можем разделить это еще больше:
maxprofit([p0], [p1..pn]) = max(maxprofit([p0], [p1]), maxprofit([p0],[p2..pn]))
Мы можем решить max([p0], [p1])
так как это базовая проблема, где прибыль = p1-p0. Теперь мы сохраняем результат и кешируем его. Продолжайте ломать maxprofit(([p0], [p2..pn])
и продолжайте кэшировать все решения.
Посмотрите на вторую подзадачу
Это проблема:
maxprofit([p0..p1], [p2..pn])
Можно разбить на:
maxprofit([p0..p1], [p2..pn]) = max(maxprofit([p0], [p2..pn]), maxprofit([p1], [p2..pn]))
Что интересно: не нужно ломаться maxprofit([p0], [p2..pn])
потому что у вас уже есть это в вашем кэше при работе над первой подзадачей. Поэтому только вторая подзадача должна быть разбита.
Я думаю, в этот момент вы уже понимаете, куда это идет. По сути, вам нужно продолжать разбивать проблему до тех пор, пока вы не попадете в базовую проблему или если проблема уже кэширована.
Вы можете улучшить его в O(n) только с тремя циклами:
- Первый цикл для построения минимальных массивов
- Второй цикл для создания максимальных массивов
- Третий цикл, чтобы найти максимальную прибыль
Более менее:
public static void main(String[] args) {
int[] stockPrices = {2, 9, 5, 7, 3, 4, 5, 6, 4, 0, 8, 7, 7, 4, 1};
int[] mins = new int[stockPrices.length - 1];
int[] minsIndex = new int[stockPrices.length - 1];
int[] maxs = new int[stockPrices.length - 1];
int[] maxsIndex = new int[stockPrices.length - 1];
int minIndex = -1;
int min = Integer.MAX_VALUE;
for (int i = 0; i < stockPrices.length - 1; i++) {
if (stockPrices[i] < min) {
min = stockPrices[i];
minIndex = i;
}
mins[i] = min;
minsIndex[i] = minIndex;
}
System.out.println("mins idx: " + Arrays.toString(minsIndex));
System.out.println("mins: " + Arrays.toString(mins));
int maxIndex = -1;
int max = -1;
for (int i = stockPrices.length - 1; i > 0; i--) {
if (stockPrices[i] > max) {
max = stockPrices[i];
maxIndex = i;
}
maxs[i - 1] = max;
maxsIndex[i - 1] = maxIndex;
}
System.out.println("maxs idx: " + Arrays.toString(maxsIndex));
System.out.println("maxs: " + Arrays.toString(maxs));
int maxProfit = -1;
int buyIndex = -1;
int sellIndex = -1;
for (int i = 0; i < stockPrices.length - 1; i++) {
int profit = maxs[i] - mins[i];
if (profit > maxProfit) {
maxProfit = profit;
buyIndex = minsIndex[i];
sellIndex = maxsIndex[i];
}
}
System.out.println("buy at: " + buyIndex + " sell at: " + sellIndex + " profit: " + maxProfit);
}