LeetCode 122 Best Time to Buy and Sell Stock II淺析（股票買入賣出的最佳時間 II）

LeetCode 122 Best Time to Buy and Sell Stock II淺析（股票買入賣出的最佳時間 II）

翻譯

話說你有一個數組，其中第i個元素表示第i天的股票價格。

設計一個算法以找到最大利潤。你可以盡可能多的進行交易（例如，多次買入賣出股票）。

然而，你不能在同一時間來多次交易。（例如，你必須在下一次買入前賣出）。

原文

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like 
(ie, buy one and sell one share of the stock multiple times). 

However, you may not engage in multiple transactions at the same time 
(ie, you must sell the stock before you buy again).

分析

其實很簡單的一道題嘛，一開始想復雜了……

舉了栗子：

// 4 7 8 2 8
最大利潤很明顯是 （8 - 4） + （8 - 2） = 10
就因為這個式子讓我想復雜了：首先要找到一個極小值4，然後找到極大值8；然後找到極小值2，然後找到極大值8；balabala……

其實換一種思路，（7 - 4) + (8 - 7) + (8 - 2)
區別在於，直接將後一個數減前一個數就好了呀，只不過如果後一個數比前一個數小的話就不考慮而已。

代碼

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