第一题
题目描述:
给定一段时间内每天的股票价格，已知你只可以买卖各一次，求最大的收益。
输入输出样例:
输入一个一维整数数组，表示每天的股票价格;输出一个整数，表示最大的收益。
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自动化测试等，微信搜索公众号：“无量测试之道”，或扫描下方二维码：
添加关注，让我们一起共同成长！