Покупка и продажа акций с 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);
}
Другие вопросы по тегам