The Crazy Broker
Solutions This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums.
To answer to the first type of queries, we need to cache the running maximums of the prices:
1 2 3 4 5 6 7 8 vector<int> prefixMax(n); auto runningMax = p.front(); prefixMax[0] = runningMax; for (auto i=1; i<n; ++i) { prefixMax[i] = max(runningMax, p[i]); runningMax = prefixMax[i]; } In C++, we have a very useful standard algorithm to perform the same routine:
[Read More]