122. 买卖股票的最佳时机
小白解法
思路
我这种解法相比于贪心算法略微有些繁琐。大致思路是找到每一段上升子序列，那么在上升子序列的结尾处，即 p r i c e s [ i ] > p r i c e s [ 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 ≤ i < n 都有 a [ i ] > a [ i − 1 ]，所有结果为 4 44
但实际上并不是进行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; } };
