最大化两个数组 B[j] − A[i] 的元素的差异，其中 j > i

Question

这不是最大利润算法，而是它的变体。

我有一个数组 A，其中 A[i] 对应 A 国 和时间 i 的计算机价格。而B[i]对应B国时间i.

的电脑价格

每个数组中的所有条目都是正整数。我想在 A 国 的某个时间 i 购买电脑，然后在 B 国 的某个时间 [=18] 出售它们=].

我需要最大化利润 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] 中的每次时间，我应该在时间 A[i] 买入并在时间 B[j] 卖出获利，其中指数j 大于索引 i.

Answer 1

为了在 O(n) 时间内做到这一点，您可以使用非常类似于 Kadane 算法的逻辑 求 sub-array.

的最大总和

总体思路是追踪之前国家A遇到的最低价格。

并在迭代的每一步，比较以当前价格出售计算机所能获得的利润B[i]（假设以最低价格购买 minA) 和 最大利润 .

国家AminA的最低价格用数组countryA[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;
}

main()

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

输出

最大化两个数组 B[j] − A[i] 的元素的差异，其中 j > i

Maximize the diff of elements of Two Arrays B[j] − A[i] where j > i

java

arrays

algorithm

dynamic-programming