小工具知识网

当前位置: 首页 > 行业知识 > 动态规划(DP)---- 买卖股票(3)

行业知识

动态规划(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黄灯怎么关?

下一篇:怎么建代理服务器?