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