Best Time to Buy and Sell Stock II

题目说明

给定一个价钱数列，prices[i]代表第i天的股票价钱。
需求是求出最大利润，一次只能持有一张股票，但可以随买随卖，即允许今天卖掉马上又买

範例

Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

限制条件和特别需求

思路

这题应用到Greedy(贪婪演算法)，详可见维基百科
简单来说，就是每一步都贪心的选择最好答案(局部最佳解)，那结果就会是最好的(全局最佳解)

根据此演算法理论，每一天是否有正利润(有的话就是局部最佳解)，加总每一天的正利润就得到最大利润(全局最佳解)。
画成下图更容易了解，红色部分全部加起来就是。

C++ 程式码

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

Python3 程式码

class Solution:    def maxProfit(self, prices: List[int]) -> int:        maxProfit = 0        for i in range(1, len(prices)):            if prices[i] > prices[i-1]:                maxProfit += prices[i] - prices[i-1]        return maxProfit