线性复杂度中的分治算法

Question

我们有一个数字数组，表示一段时间内的价格。例如，我们有[10，4，6，8，2，5，3，9，1]。我们想知道什么时候是买入和卖出以实现利润最大化的最佳时机。在这种情况下，我们将在时间[4]=2买入，在时间[7]=9卖出，获得9-2=7的利润。

在数学上，我们正在寻找a和b，其中a<=时间[b]-时间[a]最大。

使用分而治之的方法制作一个复杂度为O（nlogn）的算法有些琐碎。一段时间以来，我一直在寻找一种具有最坏情况O（n）的算法，但没有取得任何成功。如有任何帮助，我们将不胜感激。

Answer 1

这里不需要分而治之。在数组中从最旧的价格到最新的价格进行迭代，并在每一步将当前价格与迄今为止找到的最低价格进行比较。

Answer 2

如果我们作为第一步预先计算一个向量，该向量指定指数i的每个范围（0，i-1）的最小价格，然后计算如果我们在指数i处出售，我们可以获得的最大价格，我们可以在O（n）时间内轻松计算：

代码：

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

输出：

最大利润为7如果我们以指数4（价格：2）买入，以7（价格：9）卖出

实际示例

编辑：这是一种动态编程风格的方法，我现在意识到这有点过头了。如果我们按照hugomg所说的去做，那么我们只需要从左到右迭代，存储到目前为止找到的最小值。在每个新的指数i上，我们进行减法，看看是否有一个新的最大价格。时间是线性的，空间是恒定的。

Answer 3

[10，4，6，8，2，5，3，9，1]。

将上面的列表转换为O（n）中的渐变。[-6,2,2，-6,3，-2,6，-8]

应用Kadane算法找到最大子阵列O（n）：http://en.wikipedia.org/wiki/Maximum_subarray_problem

^修改以存储起始位置和结束位置。

使用kadane算法中的起始位置来查找原始数组的起始和结束位置。