买卖股票，时间复杂度为 O( n log n )

Question

编辑：
感谢你们俩的帮助，但我必须遵守 O( n log n ) 时间复杂度的界限，并且必须使用二元递归的分而治之技术。我在最初的帖子中没有说得很清楚

我有一个未排序的整数数组，我必须在第 i 天购买股票并在第 j 天卖出以获得最大利润，其中第 i（较小值）天必须在第 j（第较大的值）天。到目前为止，我已经找到了 returns 买卖天数（数组的索引值）和最大利润的解决方案，但它具有 O(n^2) 时间复杂度，我很难做到O(n log 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是数组的结尾利润 class 是我创建的一个 class 来持有买入、卖出和利润值。

我发现我需要考虑的三种情况是数组前半部分的最大利润，数组后半部分的最大利润，以及最小值在数组的第一半和最大值在数组的第二半（我已经用一个简单的 min/max 函数解决了最后一个案例来完成这部分问题）。

我被卡住了，非常感谢任何关于分而治之实施或技巧提示的帮助！

Answer 1

在 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);
}

Answer 2

只需三个循环就可以将其改进为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);
}

Answer 3

好吧，既然你表达了分而治之的需要，我再给一个答案。

假设股票价格在数组中定义：[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 log n )

Buy and Sell Stock, with O( n log n ) time complexity

java

divide-and-conquer

看第一个子问题

看第二个子问题