Finding the Largest "Ordered" Difference in Elements of an Array

Question

Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$.

I would like to design an algorithm to find the maximum profit that you can given this array of prices. Profit is made by buying at a given date $i$ and selling at a later date $j$ so that $i \leq j$.

One easy solution is the following "exhaustive algorithm":

profit = 0
for i = 1 to N-1 
  for j = i+1 to N
    if P(j) - P(i) > profit    
      profit = P(j) - P(i) 

The issue with this however is that it takes time $\Omega(N^2)$.

Can anyone think of something faster?

Answer 1

The first observation is that the strategy of buying at the lowest price or selling at the highest price does not always maximize the profit. As you also note, the simple brute-force method works by trying every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of $n$ days has $n \choose 2$ dates and $n \choose 2$ is $\Theta(n^2)$.

To achieve $o(n^2)$ running time, a simple transformation is applied to the input array. Instead of looking at the daily prices given, we will instead work with the daily change in price, where change on day $i$ is the difference between the prices after day $i-1$ and after day $i$. With a transformed input array like this, we now want to find the nonempty, contiguous subarray whose values have the largest sum. This contiguous subarray is called the maximum subarray.

For a detailed divide-and-conquer algorithm running in $\Theta(n \log n)$ time, see for example Chapter 4 of the Cormen et al. book, 3rd edition, page 68-74. The Wikipedia page also mentions Kadane's linear time algorithm and gives pseudocode.

Answer 2

I think I figured out an $O(N)$ algorithm that works for this case. The algorithm is similar to mergesort except that no sorting is done, and merging two sub-arrays together involves tracking the minimum buy price and the maximum sell price within the combined array. The tricky part involves making sure that you cannot buy before you sell.

Here is some MATLAB code that I wrote for this problem. The code assumes that the prices in the 'left' array occur before the prices 'right' array

Here is some pseudocode:

function [min_price max_price] = mergeprice(P)

N = length(P)

if N == 1 %base case for recursion

    min_price = P;
    max_price = P;

else %recursion

    %find midpoint of price list
    M = floor(N/2);

    %call mergeprice recursively to get min / max of price list
    left = P(1:M);
    right = P(M+1:N);
    [left_min_price left_max_price] = mergeprice(left);
    [right_min_price right_max_price] = mergeprice(right);

    %find the largest profit in the combined list using comparisons
    if (left_min_price <= right_min_price) && (left_max_price <= right_max_price)

        min_price = left_min_price;
        max_price = right_max_price;

    elseif (left_min_price <= right_min_price) && (left_max_price >= right_max_price)

        min_price = left_min_price;
        max_price = left_max_price;

    elseif (left_min_price >= right_min_price) && (left_max_price <= right_max_price)

        min_price = right_min_price;
        max_price = right_max_price;

    elseif (left_min_price >= right_min_price) && (left_max_price >= right_max_price)

        if left_max_price - left_min_price >= right_max_price - right_min_price

            min_price = left_min_price;
            max_price = left_max_price;

        else

            min_price = right_min_price;
            max_price = right_max_price;

        end

    end

end

end

Answer 3

Calculate The difference of contiguous profits in a array And apply kadane's algorithm on that array. You can solve this in O(n).

Answer 4

You can do it in O(n) time by using Kadane's algorithm. First transform the array A[1..n] to B[1..n] such that B[i] = Sum(A[1] to A[i]). and find the longest common subsequence in the new array