122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II   ( https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ )

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

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.

 

Constraints:

1 <= prices.length <= 3 * 10^4

0 <= prices[i] <= 10^4

因為你有上帝視角，你知道兩天之間是賺還是賠
你就把任兩天之間有賺錢的加起來，就是最大獲利

假設 profit(b, s) 代表 b 這天買，s 這天賣的獲利
如果 profit(1~n) 天的獲利會比 profit(1~n-1) 好
那profit(n-1~n)一定是正的
所以把所有可能 profit(n-1~n) 加起來，就一定會是最佳獲利
 

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        int profit = 0;

        if (prices.size() <= 1)

        {

            return profit;

        }

        for (int i=1; i<prices.size(); i++)

        {

            int thisProfit = prices[i] - prices[i-1];

            if (thisProfit > 0)

            {

                profit += thisProfit;

            }

        }

        return profit;

    }

};

參考：https://www.youtube.com/watch?v=akTjUKEP7Co&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=5