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

Question

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

我有一个未排序的整数数组，我必须在第 i 天购买股票并在第 j 天出售股票以获得最大利润，其中第 i(较小的值)天必须在第 j(较大的值)之前) 天。到目前为止，我已经找到了一个返 repo 买和销售天数(数组的索引值)和最大利润的解决方案，但它的时间复杂度为 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 是数组的结尾 Profit 类是我创建的用于保存买入、卖出和利润值的类。

我发现需要考虑的三种情况是数组前半部分的最大利润、数组后半部分的最大利润以及最小值在前半部分的情况数组的最大值位于数组的第二半(我已经使用解决最终情况的简单最小/最大函数完成了这部分问题)。

我陷入困境，任何有关分而治之实现或技巧提示的帮助将不胜感激!

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