题目描述

blablabla

样例

blablabla

算法1

(暴力循环加剪枝) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

const int N=100010;
int price[N];
int n,k,kk;
int ans=0;
using namespace std;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&price[i]);

    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            //若是后面的没有比求出的price[i]更小的 并且后面没有比price[j]更大的 就退出
            if(price[i]>k&&price[j]<kk)break;
           if(price[j]-price[i]>ans)
           {
               k=price[i];kk=price[j];
               ans=price[j]-price[i];
           }
        }
    printf("%d\n",ans);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

https://www.acwing.com/solution/content/18824/

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

 using namespace std;
 const int N=100010;
 int n;
 int ans;
int main()
{
    int k;
    cin>>n;
    cin>>k;
    while(--n)
    {
        int kk;
        scanf("%d",&kk);
        k=min(kk,k);
        ans=max(ans,kk-k);
    }
    cout<<ans<<endl;
    return 0;
}