股票买卖 题解

本文主要是介绍股票买卖 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：http://bailian.openjudge.cn/practice/4121/

解题思路

• 假设股票数组为prices
• 假设F[k][i]表示到第i天总共买卖k次时的最大利润，可以将其分为两种情况，即第i天发生了买卖和未发生买卖。
• 假如第i天没有买卖股票，那么F[k][i] = F[k][i-1]
• 假如第i天参与股票买卖，那么F[k][i] = max{prices[i] - prices[t]+F[k-1][t]},为什么是这个推导公式，因为假如F[k][i]的最优解是，第x天是k-1次的卖出，随后的第y天又买入，第i天卖出，于是F[k][i] = F[k-1][x]+prices[i]- prices[y](x<= y <=i),此时必然有F[k-1][x] =F[k-1][y],证明如下：
  • 很显然，F[k-1][y]>=F[k-1][x],假设F[k-1][y]>F[k-1][x],此时必然有F[k-1][y]+prices[i]-prices[y]>F[k][i] = F[k-1][x]+prices[i]- prices[y],这与最优解矛盾，因此必然有F[k-1][x] =F[k-1][y]，因此F[k][i]的推导公式可以写成max{prices[i] - prices[t]+F[k-1][t]}。
• 对上述进行优化，max{prices[i] - prices[i] - prices[t]+F[k-1][t]} = prices[i] +max{F[k-1][t]-prices[t]}; (0<=t<=i-1), 对于确定的i和k，每次求max{F[k-1][t]-prices[t]}都需要对t从1到i进行遍历，于是可以在循环中，求解时用一个临时变量tmp记录max{F[k-1][t]-prices[t]},t属于[0,i-1]，每次i增量时比较tmp和F[k-1][i]-prices[i]和tmp的较大值赋给tmp,再进行求解。

AC代码

代码中nums即为解题思路中的prices

#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <climits>
#include <string>
#include <algorithm>using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef const int CI;int solution(const VI& nums, CI K) {VVI F(K + 1, VI(nums.size(), 0));for (int k = 1; k <= K; ++k) {int tmp = F[k - 1][0] - nums[0];for (int i = 1; i < nums.size(); ++i) {tmp = max(F[k-1][i] - nums[i], tmp);F[k][i] = max(F[k][i - 1], nums[i] + tmp);}}return F[K][nums.size() - 1];
}int main() {ios::sync_with_stdio(false);cin.tie(0);int castCount; cin >> castCount;while (castCount--) {int N;cin >> N;VI nums(N, 0);for (auto&e : nums)cin >> e;int ans = solution(nums,2);cout << ans << endl;}return 0;
}

这篇关于股票买卖 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---