目錄
1，題目描述
英文描述
中文描述
2，解題思路
算法
3，AC代碼
4，解題過程
1，題目描述
英文描述
Say you have an array prices 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 (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [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.
Example 2:
Input: [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.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
中文描述
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個算法來計算你所能擷取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
随後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再将它們賣出。
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2，解題思路
與這一題類似@&再見螢火蟲&【LeetCode_Array_121. Best Time to Buy and Sell Stock買賣股票的最佳時機（C++）】。差別在于本題允許多次交易，且買入必須緊鄰着賣出，然後才可以進行下一次買入；
算法
- 順着上一題的思路，同樣用一個變量minPrice記錄最低價格，同時用maxPrice記錄最高價格；
- 一旦目前價格prices[i]低于最高價格，就更新ans += maxPrice - minPrice。同時minPrice與maxPrice更新為目前價格prices[i]（其實聯系實際也很容易得出結論；
- 否則就将minPrice與maxPrice更新為prices[i]；
- 注意：由于此處算法的設計，當數組最後的部分呈遞增時，不會賣出，是以需要在循環外面增加一次ans的更新ans += maxPrice - minPrice；
3，AC代碼
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0, minPrice = prices[0], maxPrice = prices[0];
if(prices.size() == 0) return 0;
for(int i = 1; i < prices.size(); ++i){
if(maxPrice > prices[i]){ // 發現目前價格prices[i]低于之前最高價格maxPrice時就賣出
ans += maxPrice - minPrice; // 賣出
maxPrice = minPrice = prices[i];
}else{ // 價格還在上漲 更新最高價格
maxPrice = prices[i];
minPrice = min(minPrice, prices[i]);
}
}
ans += maxPrice - minPrice; // 因為算法本身的原因 隻有當價格低于最高價格時才會賣出 是以數列遞增時會出錯 故補上這條語句
return ans;
}
};
4，解題過程
一發入魂o(*￣▽￣*)ブ
