[数据结构与算法]LeetCode 122. 买卖股票的最佳时机(贪心算法)

122. 买卖股票的最佳时机

小白解法

思路

我这种解法相比于贪心算法略微有些繁琐。大致思路是找到每一段上升子序列，那么在上升子序列的结尾处，即 $prices[i]>prices[i+1]$时，计算这一整段的获利。然后更新上升子序列起始位置，重复上述过程。

这样写有一个问题：例如 $[1,2,3,4,5]$? 这一判例，找不到这样一个转折点，会爆栈。我用了一个取巧的办法，给原数组增添一个小于零的元素，强行制造转折点。

代码实现

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int buy = 0, sold = 0, res = 0;
        prices.push_back(-1);
        for (int i = 0; i < prices.size()-1; i++)
        {
            if (prices[i] > prices[i + 1])
            {
                sold = i;
                res += prices[sold] - prices[buy];
                buy = i + 1;
            }
        }
        return res;
    }
};

贪心算法

思路

因为交易次数不受限，所以把所有的上坡全部收集，一定是利益最大化的。即寻找每一个 $a[i]?a[i?1]>0$? 的区间。需要说明的是，贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。例如 $[1,2,3,4,5]$?，对于所有 $1\le i<n$?? 都有 $a[i]>a[i?1]$，所有结果为 $4$

但实际上并不是进行4次买入和4次卖出，而是在第一天买入，第五天卖出。

代码实现

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i)
        {
            if (prices[i] > prices[i - 1])
            {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
};