问线性复杂度的分治算法？

EN

#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;
}