1. 題目
1.1 英文題目
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. 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 simultaneously (i.e., you must sell the stock before you buy again).
1.2 中文題目
給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，
設計一個演算法來計算你所能獲取的最大利潤，你可以盡可能地完成更多的交易（多次買賣一支股票），
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票），
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| prices = [7,1,5,3,6,4] | 7 |
| prices = [1,2,3,4,5] | 4 |
| prices = [7,6,4,3,1] | 0 |
1.4 約束條件
- 1 <= prices.length <= 3 * 104
- 0 <= prices[i] <= 104
2. 實驗平臺
IDE：VS2019
IDE版本：16.10.1
語言：c++11
3. 分析
這一題可以借鑒121題的方法，也就是Kadane's Algorithm，具體來說就是求出相鄰兩個元素間的差值，組成陣列，再將陣列中的正值加到一起，即可，具體代碼如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxpro = 0;
for (int i = 1; i < prices.size(); i++)
maxpro += max(0, prices[i] - prices[i - 1]);
return maxpro;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/289045.html
標籤：C++