??假設你有一個數(shù)組，其中第i 個元素是第i天給定股票的價格。設計算法以找到最大利潤。你可以根據(jù)需要完成盡可能多的交易（即，多次買入并賣出一股股票）。注意：您不能同時進行多筆交易（即，您必須在再次購買之前賣出股票）
??例如：
??給定數(shù)組[7,1,5,3,6,4]，算法輸出：7
??說明：第二天買入（價格：1）第三天賣出（價格：5）利潤：5-1=4，然后第四天買入（價格：3）并在第五天賣出（價格：6），利潤6-3=3，總利潤：4+3=7
??要求給出測試案例，設計算法，并給出算法在你的測試案例上計算得到的結果。

---

解法： 利用貪心算法自頂向下的策略將子問題分解為最小部分， 只有n+1天股票價格比第n天高， 就累加Sum，最后輸出Sum即可。

時間復雜度：O(n)

---

代碼展示

#include<bits/stdc++.h> #define len 6 using namespace std; int Sum = 0; void maxProfit(int *prices) {for(int i = 0; i < len-1; i++) if(prices[i+1]-prices[i] >= 0) Sum += prices[i+1]-prices[i]; }int main() {int prices[6] = {7,1,5,3,6,4};maxProfit(prices);cout << Sum; return 0; }

總結

以上是生活随笔為你收集整理的假设你有一个数组，其中第i 个元素是第i天给定股票的价格。设计算法以找到最大利润。你可以根据需要完成尽可能多的交易（即，多次买入并卖出一股股票）。注意：您不能同时进行多笔交易（即，您必须在再次购买之前的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。