If we as a first step pre-compute a vector that specifies the minimum price for each range (0, i-1) for index i, and then compute the the maximum we can make if we sell at index i, we can easily compute it in O(n) time:
Code:
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;
int main() {
vector<int> prices{10, 4, 6, 8, 2, 5, 3, 9, 1};
// sell at time [i] requires buy at minimum in range [0,i-1]
// create vector of index at minimum for each range
int currentMinimumIndex = 0;
vector<int> minimums{0};
for(size_t i = 1; i < prices.size(); ++i)
{
if (prices[i] < prices[currentMinimumIndex])
{
minimums.emplace_back(i);
currentMinimumIndex = i;
}
else
minimums.emplace_back(currentMinimumIndex);
} // O(n)
// at this point we have a lookup table for minimum in every range
// attempt to maximize amount we can get if we sell at time i buy buying at minimum for (0,i-1)
vector<int> maxSales{std::numeric_limits<int>::min()};
for(size_t i=1;i<prices.size();++i)
{
maxSales.emplace_back(prices[i] - prices[minimums[i]]);
} // O(n)
// find maximum element
auto maxSum = std::max_element(std::begin(maxSales), std::end(maxSales)); // O(n)
auto sellAt = std::distance(std::begin(maxSales), maxSum);
auto buyAt = minimums[sellAt];
std::cout << "Maximum profit is " << *maxSum << std::endl;
std::cout << "If we buy at index " << buyAt << " (price: " << prices[buyAt] << ")"
<< " and sell at " << sellAt << " (price: " << prices[sellAt] << ")" << std::endl;
return 0;
}
Output:
Maximum profit is 7
If we buy at index 4 (price: 2) and sell at 7 (price: 9)
Live Example
Edit: This is a dynamic-programming esque approach and I now realize it's a bit overkill. If we do what hugomg said Then we simply would iterate left to right, storing the minimum value found thus far. At each new index i, we perform a subtraction to see if we have a new largest price. Linear in time, constant in space.
