st申龙:股票利益 (来自科丁乐)
2021-04-01 21:44:50 来源： 浏览：1次
股票利益 (来自科丁乐)
收录于话题 请点击上面微信号关注精彩内容提高计算思维，传播编程知识，点亮未来人生！
股票利益
1. 问题描述【题目描述】小科的爸爸最近热衷于研究股市，小科天真的想，如果能够预知股票每天的价格，那么就很容易计算出什么时候买入什么时候卖出利润才能最大化。假设按照时间先后顺序给出某股票的n天的价格，请问在n天内只能买卖该股票一次可能获得的最大利润是多少？
【输入】 第一行，一个整数n，表示天数，1≤n≤10^5
接下来一行，n个整数，第i个整数，表示第i天的股票价格。整数都是1到10000以内的正整数
【输出】 一个整数，表示卖该股票一次可能获得的最大利润。
【输入样例1】6
7 1 3 5 6 4【输出样例1】5【输入样例2】5
7 6 4 3 1【输出样例2】0
说明/提示【样例说明1】在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为只能先买后卖
【样例说明2】这种情况下不需要进行交易，这样利润才能最大是0
2. 问题分析 贪心算法。
3. 算法描述最愚蠢的想法： 在这些股价中找出最小值和最大值，输出差的绝对值，显然不对，比如： 10 6 2 1，最大值为10，最小值为1，差为9，可实际盈利为0；
暴力，以每一天为基准（相当于这一天买入），假设后面每天买可获得的利润算出，然后找出这些利润中的最大值；
例：7 1 3 5 6 4
第1天买入： 后面每天卖出可分别获利： -6，-4，-2，-1，-3
第2天买入：后面每天卖出可分别获利： 2，4，5，3
第3天买入：后面每天卖出可分别获利：2，3，1
第4天买入：后面每天卖出可分别获利：1，-1
第5天买入：后面每天卖出可分别获利： -2
然后在这些盈利中找出最大值就是5
由于n=100000，以上实现我要开一个双层循环，显然超时；
#include bits/stdc++.h
using namespace std;
int a[100005];
int main()
{
int n,maxx=0;
cinn;
for(int i=1;i=n;i++)
{
cina[i];
}
for(int i=1;i=n;i++)
{
for(int j=i+1;j=n;j++)
{
maxx=max(maxx,a[j]-a[i]);
}
}
coutmaxxendl;
return 0;
}
3. 我又想，能否先找出股价的最小值，然后在后面的天数中再找出最大值，做差输出是否可以呢？
例：7 1 3 5 6 4
最小值为1，后面股价中的最大值为6，输出5
可提交有数据错误，这是为什么呢？
苦思冥想，自己造了一组数据： 25 20912 72 666 17 3 55 100
虽然数据中的最小值是3 后面最大值是100，可不是最大利润，因为前面买入9，卖出666，获利显然更大；
#include bits/stdc++.h
using namespace std;
int a[100005];
int b[100005];
int main()
{
int n,p,maxx=0,minn=999999;
cinn;
for(int i=1;i=n;i++)
{
cina[i];
if(a[i]minn)
{
minn=a[i];
p=i;
}
}
for(int i=p+1;i=n;i++)
{
maxx=max(maxx,a[i]-minn);
}
coutmaxxendl;
return 0;
}
4. 再继续思考，可以先从后往前遍历，获得当天买入，后面卖出的最大值，然后再获得每一天中的最大值即可；
例：7 1 3 5 6 4
第1天买入，后面卖出的最大盈利 -1
第2天买入，后面卖出的最大盈利 5
第3天买入，后面卖出的最大盈利 3
第4天买入，后面卖出的最大盈利 1
第5天买入，后面卖出的最大盈利 -2
然后在这些数据中找出最大值，就是5
#include iostream
#includecstring
#include cmath
#include algorithm
using namespace std;
int a[100005];
int m[100005];
int main()
{
int n,maxx=-1;
cinn;
for(int i=1;i=n;i++)
{
cina[i];
}
for(int i=n;i=1;i--)
{
maxx=max(maxx,a[i]);
m[i]=maxx; // 得到这天买入可获最大利润
}
maxx=0;
for(int i=1;i=n;i++)
{
maxx=max(maxx,m[i]-a[i]); // 再最大利润中再找出最大利润
}
coutmaxxendl;
return 0;
}
4. 代码实现#include iostream
#includecstring
#include cmath
#include algorithm
using namespace std;
int a[100005];
int m[100005];
int main()
{
int n,maxx=0;
cinn;
for(int i=1;i=n;i++)
{
cina[i];
}
for(int i=n;i=1;i--)
{
maxx=max(maxx,a[i]);
m[i]=maxx; // 得到这天买入可获最大利润
}
maxx=0;
for(int i=1;i=n;i++)
{
maxx=max(maxx,m[i]-a[i]);
}
coutmaxxendl;
return 0;
}优化一下：
#include iostream
#includecstring
#include cmath
#include algorithm
using namespace std;
int a[100005];
int m[100005];
int main()
{
int n,maxx=0,maxx1=0;
cinn;
for(int i=1;i=n;i++)
{
cina[i];
}
for(int i=n;i=1;i--)
{
maxx=max(maxx,a[i]);
maxx1=max(maxx1,maxx-a[i]);
}
coutmaxx1endl;
return 0;
}
5. 测试结果
更多精彩内容，请扫描二维码关注！
提高计算思维，编程创造未来！
