买卖股票的最佳时间-Leetcode。我知道我的代码是错误的，但我不知道为什么 [关闭]

Question

给定一个数组 prices，其中 prices[i] 是给定股票第 i 天的价格。 您希望通过选择一天购买一只股票并选择未来的另一天出售该股票来最大化您的利润。而你必须返还你所能达到的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int min=prices[0],maxAfter=prices[0],temp=0;
        for(int i=0;i<prices.size();i++)
        {
            if(prices[i]<min)
            {
                min=prices[i];
                temp=i;
            }
        }
        for(int j=temp;j<prices.size();j++)
        {
            if(prices[j]>maxAfter)
            {
                maxAfter=prices[j];
            }
        }
        return abs(maxAfter-min);
    }
};

所以我试图在整个数组中找到最小元素，然后我使用另一个 for 循环从最小元素的索引迭代到数组的末尾，这样我就可以从那个点开始找到最大元素。但它只是返回数组中的最大值。我可以解决这个问题吗？

Answer 1

你的方法不足以解决问题，因为你武断地确定答案总是与最低的总股价挂钩。那不是真的。

解决问题的简单方法涉及一个 O(N^2) 循环，因为您必须在每一天检查未来最高股票价格。然后，您可以计算当天购买的最佳利润。这意味着在另一个循环中嵌套一个 for 循环。

更聪明的方法是使用动态规划，认识到您每天都在尝试寻找数组中的最高值。因此，如果您每天以相反的顺序访问，您将已经知道未来最高股票价格。这意味着问题实际上可以在 O(N) 时间内解决。

int maxProfit(const vector<int>& prices)
{
    if (prices.empty()) return 0;
    int max_profit = 0;
    int max_price = prices.back();
    for (auto it = prices.rbegin() + 1; it != prices.rend(); it++) {
        int price = *it;
        max_profit = std::max(max_profit, max_price - price);
        max_price = std::max(max_price, price);
    }
    return max_profit;
}

需要注意的是，我不是在计算绝对差异。在正常的股票交易中，您可以通过做空股票获利。但这本质上意味着卖在买之前。由于原始问题提到您buy然后sell，一个是假设不允许做空股票。

Answer 2

你的逻辑不对。我认为你必须通过以下方式解决这个问题：

int maxProfit(std::vector<int>& prices) {
    std::vector<int>::size_type i;
    std::vector<int> sx(prices.size());
    auto curr{ prices.back() };
    for (i = prices.size() - 2; i != -1; --i) {
        sx[i] = curr;
        curr = std::max(curr, prices[i]);
    }
    int cand, ret{ 0 };
    for (i = 0; i + 1 != prices.size(); ++i) {
        cand = sx[i] - prices[i];
        if (cand > ret) {
            ret = cand;
        }
    }
    return ret;
}

sx 是后缀数组，其中 sx[i] 包含区间 [i + 1, sx.size()) 中寻求的最大 curr。对于 i = sx.size() - 1 最大值为 0 仅仅是因为它不存在。

cand 是您可以从存储在价格中的第 i 笔交易中获得的最大利润。

ret 是您正在寻找的答案，即大于 0 的最大 cand。