這不是最大利潤演算法，而是它的一種變體。
我有一個陣列A，A[i]對應A國電腦的價格和時間i。并且B[i]對應B國電腦的價格和時間i。
每個陣列中的所有條目都是正整數。我想在某個時間在A 國i購買計算機，然后在稍后的某個時間在B 國j > i出售它們。
我需要最大化利潤 B[j] ? A[i]。
例子：
A = [40, 18, 20, 25, 12, 13, 19, 20, 5, 7, 3]
B = [15, 50, 5, 30, 34, 19, 28, 33, 20, 20, 20]
最大可能的利潤是B[7] ? A[4] = 33 ? 12 = 21，所以產量應該是21。
我希望它在O(n)中運行。
這就是我到目前為止所擁有的。
static int maxProfit(int pricesA[], int pricesB[]) {
int maxProfit = 0;
for (int i = 0; i < pricesA.length; i ) {
for (int j = 1; j < pricesB.length; j ) {
if (pricesB[j - 1] > pricesA[i]) {
maxProfit = pricesB[j - 1] - pricesA[i];
}
}
}
return maxProfit;
}
但是，我在一次出售計算機時遇到了麻煩j > i。現在，我每次都在比較B[j]應該A[i]是什么時候買，然后在 index大于 index的時候A[i]賣掉它以獲取利潤。B[j]ji
uj5u.com熱心網友回復：
為了在O(n)時間內做到這一點，您可以使用與Kadane 演算法非常相似的邏輯來查找子陣列的最大和。
總體思路是跟蹤之前在A 國遇到的最低價格。
并且在迭代的每一步，將計算機以當前價格B[i]（假設它們以最低價格購買 minA）所獲得的利潤與最大利潤進行比較。
使用陣列中的第一個元素初始化的國家A 的 最低價格。并且在每個迭代步驟中，它都與 element 的值進行比較。minAcountryA[0]countryA[i - 1]
每一步的最佳利潤將是countryB[i] - minA，其中minA是 中的最小值countryA[0] ... countryA[i - 1]。
給定陣列的長度不同或由少于 2元素組成的情況表示輸入資料不正確的情況，因此IllegalArgumentException被拋出。
public static int getMaxProfit(int[] countryA, int[] countryB) {
if (countryA.length != countryB.length || // will lead to IndexOutOfBoundsException
countryB.length < 2) { // impossible to fulfil requirement: B[j] - A[i] where j > i
throw new IllegalArgumentException();
}
int minA = countryA[0];
int maxProfit = countryB[1] - countryA[0];
for (int i = 2; i < countryB.length; i ) {
minA = Math.min(countryA[i - 1], minA);
maxProfit = Math.max(countryB[i] - minA, maxProfit);
}
return maxProfit;
}
主要的（）
public static void main(String[] args) {
int[] countryA = {40, 18, 20, 25, 12, 13, 19, 20, 5, 7, 3};
int[] countryB = {15, 50, 5, 30, 34, 19, 28, 33, 20, 20, 20};
System.out.println(getMaxProfit(countryA, countryB));
}
輸出
21
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/443163.html