Stock Maximize · Coding Gym

Solutions

A good strategy consists in selling one share only if that increases someday in the future. The best time to sell it corresponds to highest price reached after the day we buy the stock.

For instance:

1

2 5 100

The best strategy is:

at day 1 we buy the stock and we pay 2
at day 2 we buy the stock and we pay 5 (we don’t sell the stock bought before yet)
at day 3 we sell both the stocks by earning 100-2 + 100-5 = 193

In other words, the best strategy consists in buying every stock at price \(p_i\) only if in the future the stock price \(p_i\) is surpassed. In the example above, 2 and 5 are surpassed by 100. 100 itself is not surpassed though.

Algorithmically, for each price \(p_i\) at position \(i\) we need to find the maximum price \(m_i\) that is greater than \(p_i\) (if any) from \(i\) to \( N \). Then we sum to our total profit \(m_i - p_i\).

The tricky part is finding such a maximum value in an efficient way. The quadratic solution is easy: for each price \(p_i\) we just iterate forward to find the maximum price that is greater than \(p_i\). The code is left to the reader.

To find an efficient solution we can think…backwards! We iterate the prices backwards and we keep track of the maximum price so far:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


long stockmax(const vector<long>& prices) 
{
    auto runningMax = 0l;
    auto profit = 0l;
    for (int i=prices.size()-1; i>=0; --i)
    {
        runningMax = max(runningMax, prices[i]);
        profit += runningMax - prices[i];
    }
    return profit;
}

This solution is linear.

Emerging patterns

Two patterns emerge from the snippet above:

prefix sum
zip | map | reduce

So we can re-write the code this way:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


long stockmax(const vector<long>& prices) 
{
    vector<long> psum(prices.size());
    partial_sum(rbegin(prices), rend(prices), rbegin(psum), 
        [](auto l, auto r){ return max(l, r); });
    
    auto profit = 0l;
    for (auto i=0; i<psum.size(); ++i)
    {
        profit += psum[i] - prices[i];
    }
    return profit;
}

And then:

1
2
3
4
5
6


long stockmax(const vector<long>& prices) 
{
    vector<long> psum(prices.size());
    partial_sum(rbegin(prices), rend(prices), rbegin(psum), [](auto l, auto r){ return max(l, r); });
    return inner_product(begin(psum), end(psum), begin(prices), 0l, plus<>{}, minus<>{});
}

In C++20 we can use ranges to remove both the additional storage and the extra scan:

1
2
3


auto maxs = view::partial_sum(views::reverse(stock), [](auto l, auto r){ return std::max(l, r); });
zipped = view::zip_with(std::minus<>{}, maxs, views::reverse(stock));
cout << ranges::accumulate(zipped, 0);

Since Python 3.2 we can use itertools.accumulate that makes an iterator returning accumulated “sums” (customizable):

1
2
3


maxs = accumulate(reversed(stock), max)
zipped = map(lambda x: x[0]-x[1], zip(maxs, reversed(stock)));
print(sum(zipped))

For the curious C++ developer, here are two related posts by Marco Arena:

An alternative approach using a stack by Andrea Battistello:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


function stockmax(prices) {
    var stack = [];

    prices.forEach((e,i)=>{
        while (stack.length > 0 && stack[stack.length-1].value <= e){
            stack.pop();
        }
        stack.push({value:e,index:i});
    });
    
    
    var total = 0;
    var currentStackIndex = 0;
    var prefixSum = 0;
    var currentLength = 0;
    for (var i = 0; i < prices.length; i++) {
        prefixSum += prices[i];
        currentLength++;
        if (currentStackIndex >= stack.length || i >= stack[currentStackIndex].index) {
            total += currentLength*prices[i] - prefixSum;
            currentStackIndex++;
            prefixSum = 0;
            currentLength = 0;
        }
    }
    
    return total;

}

prefix sum patterns