阅读量:0
描述
最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。
假设阿福已经准确预测出了某只股票在未来 N 天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。
同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可以第二次买入。
现在，阿福想知道他最多可以获得多少利润。
答案:
#include<bits/stdc++.h> using namespace std; int a[100005]; int x[100005];//第i天买入的最大利润 int y[100005];//第i天买出的最大利润 int main(){ int t,n; cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i];//第i天的股票价格 } memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); //(1)第i天买入的最大利润=后几天的最高价-第i天的价格 int g=a[n]; for(int i=n;i>=1;i--){ g=max(g,a[i]); x[i]=g-a[i]; } //(2)第i天卖出的最大利润=第i天的价格-前几天的最低价 int d=a[1]; for(int i=1;i<=n;i++){ d=min(d,a[i]); y[i]=max(y[i-1],a[i]-d); } //第i天最大利润=第i天买入的最大利润+第i天卖出的最大利润 int Max=-99999; for(int i=1;i<=n;i++){ Max=max(Max,x[i]+y[i]); } cout<<Max<<endl; } return 0; } 