编辑：
我感谢你们两位的帮助，但我必须遵守O(n log n(时间完整性的界限，并且必须使用二进制递归的分治技术。我在最初发布时没有明确表示
我有一个未排序的int数组，我必须在第I天购买股票，并在第j天出售，以获得最大利润，其中第I天(价值较小(必须在第j日(价值较大(之前。到目前为止，我已经找到了一个返回买卖天数(数组的索引值(和最大利润的解决方案，但它具有O(n^2(时间复杂性，我很难达到O(nlogn(时间复杂性并实现分治
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在数组的末尾利润类是我创建的一个类，用于持有买入、卖出和利润值。
我发现我需要考虑的三种情况是阵列前半部分的最大利润，以及最小值在数组的第一半，最大值在数组第二半的情况(我已经用一个简单的min/max函数完成了这部分问题，它解决了最后的情况(。
我被卡住了，任何关于分而治之的实现或技巧的帮助都将不胜感激！
在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);
}
只需三个循环就可以将其改进为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);
}
既然你表达了使用分而治之的需要，我将给出另一个答案。
假设股票价格定义在一个数组中：[p0，p1，…，pn]。
我们可以将这个问题划分为子问题，并将其定义为子问题。
max profit = max(maxprofit([p0], [p1..pn]), maxprofit([p0..p1], [p2..pn]), ..., maxprofit([p0..pn-1], [pn]))
最大利润的第一个论点是买入价格的数组，第二个论点是卖出价格的数组。
调查第一个子问题
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])，因为它已经在缓存中了。因此，只需要分解第二个子问题。
我想在这一点上，你已经明白了这一点。基本上，你需要不断地分解问题，直到你进入一个基本问题，或者如果问题已经缓存。