首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7381

股票买卖 最近越来越多的人都投身股市,阿福也有点心动了。谨记着“股市有风险,入市需谨慎”,阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某…

股票买卖

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

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

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

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

时间限制:1000

内存限制:65536

输入

输入的第一行是一个整数 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

提示

对于第一组样例,阿福可以第 1 次在第 1 天买入(价格为 5 ),然后在第 2 天卖出(价格为 14 )。第 2 次在第 3 天买入(价格为 -2 ),然后在第 7 天卖出(价格为 17 )。一共获得的利润是 (14 - 5) + (17 - (-2)) = 28 对于第二组样例,阿福可以第 1 次在第 1 天买入(价格为 6 ),然后在第 2 天卖出(价格为 8 )。第 2 次仍然在第 2 天买入,然后在第 2 天卖出。一共获得的利润是 8 - 6 = 2 对于第三组样例,由于价格一直在下跌,阿福可以随便选择一天买入之后迅速卖出。获得的最大利润为 0

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1: //基本解法 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 100005 #define INF 0x3f3f3f3f int t, n, ans, a[N], de[N], db[N], dpe[N], dpb[N]; int main() {     int mn, mx;     scanf("%d", &amp;t);     while(t--)     {         memset(dpe, 0, sizeof(dpe));         memset(dpb, 0, sizeof(dpb));         scanf("%d", &amp;n);         for(int i = 1; i &lt;= n; ++i)             scanf("%d", &amp;a[i]);         mn = a[1];         for(int i = 1; i &lt;= n; ++i)         {             mn = min(mn, a[i]);             de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。             dpe[i] = max(dpe[i-1], de[i]);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         mx = a[n];         for(int i = n; i &gt;= 1; --i)         {             mx = max(mx, a[i]);             db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。             dpb[i] = max(dpb[i+1], db[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值          for(int i = 1; i &lt; n; ++i)//枚举分割点             ans = max(ans, dpe[i]+dpb[i+1]);         printf("%d\n", ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//优化:变递推为迭代 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 100005 #define INF 0x3f3f3f3f int t, n, ans, mn, mx, a[N], dpe[N], dpb[N]; int main() {     scanf("%d", &amp;t);     while(t--)     {         memset(dpe, 0, sizeof(dpe));         memset(dpb, 0, sizeof(dpb));         scanf("%d", &amp;n);         for(int i = 1; i &lt;= n; ++i)             scanf("%d", &amp;a[i]);         mn = a[1];         for(int i = 1; i &lt;= n; ++i)         {             mn = min(mn, a[i]);             dpe[i] = max(dpe[i-1], a[i] - mn);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         mx = a[n];         for(int i = n; i &gt;= 1; --i)         {             mx = max(mx, a[i]);             dpb[i] = max(dpb[i+1], mx - a[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值          for(int i = 1; i &lt; n; ++i)//枚举分割点             ans = max(ans, dpe[i]+dpb[i+1]);         printf("%d\n", ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2: #include&lt;bits/stdc++.h&gt; using namespace std; #define N 100005 #define INF 0x3f3f3f3f int t, n, mn, mx, mxde, ans, a[N], de[N], db[N]; int main() {     scanf("%d", &amp;t);     while(t--)     {         scanf("%d", &amp;n);         for(int i = 1; i &lt;= n; ++i)             scanf("%d", &amp;a[i]);         mn = a[1];         for(int i = 1; i &lt;= n; ++i)         {             mn = min(mn, a[i]);             de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。         }         mx = a[n];         for(int i = n; i &gt;= 1; --i)         {             mx = max(mx, a[i]);             db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。         }         mxde = ans = -INF;//ans:原序列中不相交的两个区间的区间差值加和的最大值          for(int i = 1; i &lt; n; ++i)//枚举分割点         {             mxde = max(mxde, de[i]);//mxde为第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。              ans = max(ans, mxde + db[i+1]);         }         printf("%d\n", ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; #include&lt;string&gt; #include&lt;cstdlib&gt; #include&lt;queue&gt; #include&lt;vector&gt; #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 100001 #define MOD 100001 #define E 1e-12 using namespace std; int a[N],f1[N],f2[N]; int main() {     int t,ans;     scanf("%d",&amp;t);     while(t--)     {         int n;         scanf("%d",&amp;n);         for(int i=1;i&lt;=n;i++)             scanf("%d",&amp;a[i]);           int minn=INF,maxx=-INF;         f1[0]=0;         f2[n+1]=0;         for(int i=1;i&lt;=n;i++)         {             minn=min(minn,a[i]);             f1[i]=max(f1[i-1],a[i]-minn);         }         for(int i=n;i&gt;=1;i--)         {             maxx=max(maxx,a[i]);             f2[i]=max(f2[n+1],maxx-a[i]);         }           int ans=-INF;         for(int i=1;i&lt;=n;i++)             ans=max(ans,f1[i]+f2[i]);         printf("%d\n",ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法4 动态规划 #include &lt;bits/stdc++.h&gt;   using namespace std;  int t,n,w[100005],dp[1000005][2]; int main() { cin&gt;&gt;t;//测试案例的数量 int k=2;//最大买卖次数 while(t--){ cin&gt;&gt;n; for(int i=1;i&lt;=n;i++) cin&gt;&gt;w[i]; memset(dp,0,sizeof(dp));//将f数组的所有元素置为0 for(int i=0;i&lt;=k;i++) dp[i][1]=-1e6;//将f[j][1]列中的所有元素置为负无穷大 for(int i=1;i&lt;=n;i++) for(int j=1;j&lt;=k;j++){ //第j次购入股票 dp[j][0]=max(dp[j][0],dp[j][1]+w[i]); //第j次抛售股票 dp[j][1]=max(dp[j][1],dp[j-1][0]-w[i]); } cout&lt;&lt;dp[k][0]&lt;&lt;endl; } return 0; }</pre>
这道题暂未补解析。