第一題
題目描述:
????給定一段時間內每天的股票價格，已知你只可以買賣各一次，求最大的收益，
輸入輸出樣例:
????輸入一個一維整數陣列，表示每天的股票價格;輸出一個整數，表示最大的收益，
Input：[7,1,5,3,6,4]
Output:5
????在這個樣例中，最大的利潤為在第二天價格為 1 時買入，在第五天價格為 6 時賣出，
題解:
????我們可以遍歷一遍陣列，在每一個位置 i 時，記錄 i 位置之前所有價格中的最低價格，然后 將當前的價格作為售出價格，查看當前收益是不是最大收益即可，
int maxProfit(vector<int>& prices) { int sell = 0, buy = INT_MIN; for (int i = 0; i < prices.size(); ++i) { buy = max(buy, -prices[i]); sell = max(sell, buy + prices[i]); } return sell; }
第二題
題目描述:
????給定一段時間內每天的股票價格，已知你只可以買賣各 k 次，且每次只能擁有一支股票，求 最大的收益，
輸入輸出樣例:
????輸入一個一維整數陣列，表示每天的股票價格;以及一個整數，表示可以買賣的次數 k，輸 出一個整數，表示最大的收益，
Input: [3,2,6,5,0,3], k = 2
Output:7
????在這個樣例中，最大的利潤為在第二天價格為 2 時買入，在第三天價格為 6 時賣出;再在第 五天價格為 0 時買入，在第六天價格為 3 時賣出，
題解:
????如果 k 大約總天數，那么我們一旦發現可以賺錢就進行買賣，如果 k 小于總天數，我們可以 建立兩個動態規劃陣列 buy 和 sell，對于每天的股票價格，buy[j] 表示在第 j 次買入時的最大收 益，sell[j] 表示在第 j 次賣出時的最大收益，
// 主函式 int maxProfit(int k, vector<int>& prices) { int days = prices.size(); if (days < 2) { return 0; } if (k >= days) { return maxProfitUnlimited(prices); } vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0); for (int i = 0; i < days; ++i) { for (int j = 1; j <= k; ++j) { buy[j] = max(buy[j], sell[j-1] - prices[i]); sell[j] = max(sell[j], buy[j] + prices[i]); } } return sell[k]; } // 輔函式 int maxProfitUnlimited(vector<int> prices) { int maxProfit = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] > prices[i-1]) { maxProfit += prices[i] - prices[i-1]; } } return maxProfit; }
Swift 編程語言版本
func maxProfit(_ prices: [Int]) -> Int { calculateProfit(prices, 0) } func calculateProfit(_ prices: [Int], _ index: Int) -> Int { if index >= prices.count {return 0} var max = 0 for i in 0..<prices.count { var maxProfit = 0 for j in i+1..<prices.count { if prices[i] < prices[j] { let curProfit = prices[j] - prices[i] + calculateProfit(prices, i + 1) if curProfit > maxProfit { maxProfit = curProfit } } } if maxProfit > max { max = maxProfit } } return max }
歡迎關注【無量測驗之道】公眾號，回復【領取資源】
Python編程學習資源干貨、
Python+Appium框架APP的UI自動化、
Python+Selenium框架Web的UI自動化、
Python+Unittest框架API自動化、
資源和代碼 免費送啦~
文章下方有公眾號二維碼，可直接微信掃一掃關注即可，
備注：我的個人公眾號已正式開通，致力于測驗技術的分享，包含：大資料測驗、功能測驗，測驗開發，API介面自動化、測驗運維、UI自動化測驗等，微信搜索公眾號：“無量測驗之道”，或掃描下方二維碼：
添加關注，讓我們一起共同成長！
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/286144.html
標籤：iOS