Search code examples
javaarraysalgorithmdynamic-programming

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

This is not the max-profit algorithm, but a variation of it.

I have an array A, where A[i] corresponds to the price of computers in country A and time i. And B[i] corresponds to the price of computers in country B and time i.

All entries in each array are positive integers. I want to buy computers in country A at some time i and then sell them in country B at some later time j > i.

I need to maximize profit B[j] − A[i].

Example:

A = [40, 18, 20, 25, 12, 13, 19, 20, 5, 7, 3]

B = [15, 50, 5, 30, 34, 19, 28, 33, 20, 20, 20]

The maximum possible profit is B[7] − A[4] = 33 − 12 = 21, so the output should be 21.

I want this to run in O(n).

This is what I have so far.

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

However, I'm having trouble with getting the selling the computer at a time j > i part. Right now, I'm comparing every time in B[j] with A[i] when it should be that I buy at time A[i] and sell it for a profit at time B[j] where index j is greater than index i.

Solution

  • In order to do that in O(n) time you can use the logic that very is similar to Kadane's algorithm for finding the maximum sum of a sub-array.

    The overall idea is to track the minimum price previously encountered for country A.

    And at each step of iteration, compare the profit that can be obtained by selling the computers at the current price B[i] (assuming that they were bought at a minimum price minA) with the maximum profit.

    Minimum price for country A minA initialized with the first element in the array countryA[0]. And at each iteration step it's being compared with the value of element countryA[i - 1].

    The best possible profit for each step will be countryB[i] - minA, where minA is the smallest value among countryA[0] ... countryA[i - 1].

    The case when the given arrays are of different length or comprised of less than 2 elements represents the situation when the input data is incorrect, therefore IllegalArgumentException is thrown.

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

    Output

    21