首页 > 代码库 > 【noi 2.6_8464】股票买卖（DP）
【noi 2.6_8464】股票买卖（DP）
题意：N天可买卖2次股票，问最大利润。
解法：f[i]表示前 i 天买卖一次的最大利润，g[i]表示后 i 天。
注意——当天可以又买又卖，不要漏了这个要求；数据较大。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 #define N 100010 8 #define INF 1000010 9 int a[N],f[N],g[N];10 int mmin(int x,int y) {return x<y?x:y;}11 int mmax(int x,int y) {return x>y?x:y;}12 13 int main()14 {15 int T,n;16 scanf("%d",&T);17 while (T--)18 {19 scanf("%d",&n);20 int ans=0,mn=INF,mx=-INF;21 f[0]=g[n+1]=-INF;22 for (int i=1;i<=n;i++)23 {24 scanf("%d",&a[i]);25 mn=mmin(mn,a[i]);26 f[i]=mmax(f[i-1],a[i]-mn);27 }28 for (int i=n;i>=1;i--)29 {30 mx=mmax(mx,a[i]);31 g[i]=mmax(g[i+1],-a[i]+mx);32 ans=mmax(ans,f[i]+g[i]);33 }34 printf("%d\n",ans);35 }36 return 0;37 }
【noi 2.6_8464】股票买卖（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。