行业知识
动态规划(DP)---- 买卖股票(3)
2026-11-21 00:11:26
来源:互联网转载
���定一个长度为 N 的数组,数组中的第 i个数字表示一个给定股票在第 i 天的价格。
()设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
()输入格式
第一行包含整数 N,表示数组长度。
第二行包含 N 个不大于 10000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
1≤N≤1e5
输入样例1:
83 3 5 0 0 3 1 4
输出样例1:
6
分析这道题目,这里就给大家带来动态规划的做法了, 由于这里限制只能买卖两次,所以这里咱们就要设置新的变量参数:1 第一次买入 ; 2 第一次卖出 ; 3 第二次买入 ; 4 第二次卖出。
所以根据这个我们就可以推出状态转移方程:
dp[i][1] = max(dp[i - 1][1] ,-a[i]);dp[i][2] = max(dp[i - 1][2] , dp[i - 1][1] + a[i]);dp[i][3] = max(dp[i - 1][3] , dp[i - 1][2] - a[i]);dp[i][4] = max(dp[i - 1][4] , dp[i - 1][3] + a[i]);
这里就不仔细讲解了,提供一个思路,可以结合我的前几篇文章,提到了思路。
那么完整代码展示:
#include #include #include using namespace std;const int N = 101010;int n;int dp[N][4];int a[N];int main(){ cin >> n; for(int i = 0;i > a[i]; dp[0][1] = -a[0]; dp[0][3] = -a[0]; for(int i = 1;i n; for(int i = 0;i > a[i]; dp[1] = -a[0]; dp[3] = -a[0]; for(int i = 1;i n >> k; for(int i = 0;i > a[i]; for(int i = 1;i > k; for(int i = 0;i > a[i]; for(int i = 1;i
上一篇:服务器面板ps黄灯怎么关?
下一篇:怎么建代理服务器?