入门问题:Maximum Profit"/>
竞赛训练1 入门问题:Maximum Profit
竞赛训练1 入门问题:Maximum Profit
题目来源:《挑战程序设计竞赛》
题目:外汇交易可以通过兑换不同国家的货币以赚取汇率差。比如1美元兑换100日元时购入1000美元,然后等汇率变动到一美元兑换108日元时再卖出,这样就可以赚取(108-100)*1000=8000日元。现在请将某货币在t时刻的价格RiRi(i=0,1,2…n-1)作为输入数据,计算出价格差Rj-Ri(其中j>i)的最大值。
输入:第一行输入整数n,接下来n行依次给整数Ri(i=0,1,2…n-1)赋值。
输出:在单独一行输出最大值。
限制:2≤n≤200000 1≤Rt≤10^9
输入示例1
6
5
3
1
3
4
3输出示例1
3
输入示例2
3
4
3
2输出示例2
-1
虽然简单,但是对于我这种菜鸟来说,还是有坑的……如果不看书的话我估计就真踩进去了:
1.应该考虑Rt单调递减的情况,比方说示例2
2.当n=200000时,如果是复杂度为O(n^2)的算法,程序将会无法处理
算法1
最简单的算法,直接一个二重循环将每一种利润算出来,同时设置一个最大值maxv,每算出一个利润值就和maxv比较,如果大于maxv就将该利润值赋值给maxv,最后循环结束,也就得出了最大利润。但是复杂度是O(n^2),对于n=200000时的情况无法处理。
#include <iostream>
using namespace std;int main()
{int maxv=-99,n,R[100];cin>>n;for(int i=0;i<n;++i){cin>>R[i];}for(int j=1;j<n;++j){for(int i=0;i<j;++i){if(maxv<R[j]-R[i]){maxv=R[j]-R[i];}}}cout<<endl<<maxv;return 0;
}
算法2
只用一重循环,遍历Rt,在循环变量i自增的过程中,将从第一个元素到当前元素中最小的Ri值记录到变量minv中,minv的初值可以设置为R0,在遍历Rt的过程中比较每一个Ri-minv和maxv的大小,如果maxv<Ri-minv,那么maxv当然就要重新赋值为Ri-minv,在判断完maxv之后才可以对minv与当前Ri进行比较,如果minv>Ri就将minv更新为Ri的值。注意一定要先判断maxv才可以判断minv,先判断minv的话,如果将minv更新后为Ri的值,那么在下一步判断maxv的操作时就会出现Ri-minv=0的情况,也会缺少Ri-minv与maxv的一次比较(这里的minv是没有更新为Ri的)。
这种算法复杂度为O(n),可以处理n=200000的情况。
#include <iostream>
using namespace std;int main(){int minv,maxv=-2,n,R[100];cin>>n;for(int i=0;i<n;++i){cin>>R[i];} minv=R[0];for(int i=1;i<n;++i){if(maxv<R[i]-minv)maxv=R[i]-minv;if(minv>R[i])minv=R[i];}cout<<endl<<maxv;return 0;}
更多推荐
竞赛训练1 入门问题:Maximum Profit
发布评论