Arron Maximum Profit · Coding Gym

Solutions

This problem is an application of Find the Maximum Difference.

Basically, we need to find out the maximum difference between two numbers in the given array \(max(prices[j] - prices[i])\) with \(i<j\).

The bruce force approach is quadratic and does not pass all test cases: for each element we linearly find the biggest next value.

As discussed in Find the Maximum Difference, the general solution schema is the following:

1
2
3
4
5
6
7
8
9


auto currMin = INT_MAX;
auto currMax = 0;
for (auto i : prices)
{
    currMin = min(currMin, i);
    currMax = max(i - currMin, currMax);
}

cout << currMax;

As long as we iterate the array, currMin keeps track of the smallest element along the way. Every time we update also the global maximum difference by comparing it with the current difference.

Emerging Patterns

The code above can be decomposed into the following steps:

calculate the array of minimum prices from \(0\) to \(N-1\)
subtract the array of prices from the array of minimum prices
find the maximum value of that difference array

For example:

1

prices: 7,1,5,3,6,4

1
2
3
4


prices: 7,1,5,3,6,4
mins:   7,1,1,1,1,1
delta:  0,0,4,2,5,3
maxval:         ^

Here is a possible implementation in C++:

1
2
3
4


vector<int> mins(prices.size());
partial_sum(begin(prices), end(prices), begin(mins), [](auto l, auto r) { return min(l,r); });
transform(begin(prices), end(prices), begin(mins), begin(prices), minus<>());
return !prices.empty() ? *max_element(begin(prices), end(prices)) : 0;

transform | reduce (max_element is an application of reduce) boils down to inner_product (or C++17 transform_reduce):

1
2
3
4
5
6


vector<int> mins(prices.size());
partial_sum(begin(prices), end(prices), begin(mins), [](auto l, auto r) { return min(l,r); });
cout << inner_product(begin(prices), end(prices), begin(mins), 0, 
                    [](auto l, auto r){ return max(l, r); },
                    minus<>{}
                    );

C++20 ranges make everything clearer and more efficient (no extra space and only one pass):

1
2


auto mins = views::partial_sum(v, [](auto l, auto r){ return std::min(l, r); });
cout << max(views::zip_with(std::minus<>{}, v, mins));

It’s interesting to note that the “dual” solution is valid as well. For example:

1
2
3
4
5
6


vector<int> maxs(prices.size());
partial_sum(rbegin(prices), rend(prices), rbegin(maxs), [](auto l, auto r) { return max(l,r); });
return inner_product(begin(maxs), end(maxs), begin(prices), 0, 
                    [](auto l, auto r){ return max(l, r); },
                    minus<>{}
                    );

prefix sum patterns