题目难度:二星
考察点:贪心

方法1:暴力

1.分析:

我们直接按照这个题的题意进行枚举,即假设在第i(0<=i<n)天买入,在第j(i<j<n)天卖出,那么得到的结果显然就是a[j]-a[i],我们将这所有的a[j]-a[i]取最大值就是我们要的答案。    

算法实现:
(1). 需要处理一下输入,即while(cin>>a[n++]);
(2). 将得到的数组a进行在第i天买入和第j天卖出,计算并比较a[j]-a[i]的值。
(3). 输出所有结果的最大值ans即可。

2.复杂度分析:

时间复杂度:O(n^2) 
空间复杂度:O(n)

3.代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int a[MAXN];
int main() {
    int n = 0;
    while(cin>>a[n++]);
    int ans = 0;
    for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) ans = max(ans, a[j]-a[i]);
    cout<<ans<<endl;
    return 0;
}

方法2:贪心

1.分析:

题目中要求只能一次买入和卖出操作,那么我们就直接记录之前遍历过的最低价格mn,然后对于当前的输入x来说,我们计算x-mn得到的就是在当前卖出获得的最大收益,那么我们将这个最大收益保留下来与ans进行比较大小,保留更大的收益给ans,同时更新最小值即mn=min(mn,x),然后我们输出最终的结果ans就可以了。

算法实现:
(1). 需要处理一下输入,即while(cin>>x);
(2). 对于每次输入的x求一下x减去之前的最小值的结果,将这个结果与ans取最大值,然后在比较当前x与之前的最小值的大小,保留最小值。
(3). 输出ans即可。

2.复杂度分析:

时间复杂度:O(n) 
空间复杂度:O(n)

3.代码:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, mn = INT_MAX, ans = 0;
    while(cin>>x){
        ans = max(ans, x-mn);
        mn = min(mn, x);
    }
    cout<<ans<<endl;
    return 0;
}