7663: 股票买卖 动态规划/线性dp

描述

最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。

假设阿福已经准确预测出了某只股票在未来N天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。

同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可以第二次买入。

现在，阿福想知道他最多可以获得多少利润。

输入

输入的第一行是一个整数T(T≤50)，表示一共有T组数据。

接下来的每组数据，第一行是一个整数N(1≤N≤100,000)，表示一共有N天。第二行是 N 个被空格分开的整数，表示每天该股票的价格。该股票每天的价格的绝对值均不会超过1,000,000。

输出

对于每组数据，输出一行。该行包含一个整数，表示阿福能够获得的最大的利润。

样例输入

3
7
5 14 -2 4 9 3 17
6
6 8 7 4 1 -2
4
18 9 5 2

样例输出

28
2
0

状态定义：定义两个数组，l和r

l[i]表示在第i天卖掉股票的最大利润

r[i]表示在第i天买股票的最大利润

状态初始化：全部为0

状态转移方程：l[i]=max(l[i-1],a[i]-buy1);//其中1为第i天之前价格的最低

r[i]=max(r[i-1],buy2-a[i]);//2表示第i天及以后价格的顶峰

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+10;
 4 int l[N],r[N],a[N];
 5 //l[i]在第i天卖出股票最大利润
 6 //r[i]在第i天买入股票最大利润 
 7 int b1,b2;
 8 int n;
 9 int main()
10 {
11     int t; cin>>t;
12     while(t--)
13     {
14         cin>>n;
15         memset(l,0,sizeof(l));
16         memset(r,0,sizeof(r));
17         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
18         b1 = a[1]; //最小买入价 
19         b2 = a[n]; //最大卖出价 
20         for(int i=1;i<=n;i++)
21         {
22             l[i] = max(l[i-1],a[i]-b1); //卖出利润：第i天股价a[i]-买入价b1 
23             b1 = min(b1,a[i]);
24         }
25         for(int i=n;i>=1;i--)
26         {//买入利润：卖出价b2-买入价a[i]，所以需要从第n天往前看才能知道哪一天的股价a[i]卖出利润大 
27             r[i] = max(r[i+1],b2-a[i]);
28             b2 = max(b2,a[i]);
29         }
30         int sum = 0;
31         for(int i=1;i<=n;i++)
32         {
33             sum = max(sum,l[i]+r[i]); //第i天卖出最大利润+买入时最大利润相加 
34         }
35         if(sum<0)cout<<0<<endl; //负利润不如不买 
36         else cout<<sum<<endl;
37     }
38      return 0;
39 }