C++14(g++5.4) 解法, 执行用时: 132ms, 内存消耗: 8308K, 提交时间: 2020-08-27 11:41:36

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a[1001000],s[1001000];

int main()
{
    ll n;
    scanf("%lld",&n);
    ll top=0;
    for(ll i=0;i<n;i++) scanf("%lld",&a[i]);
    for(ll i=0;i<n;i++){
        while(top>1&&(a[i]-a[s[top]])*(s[top]-s[top-1])<=(a[s[top]]-a[s[top-1]])*(i-s[top]))  top--;
        s[++top]=i;
    }
    ll x=0,y=1;
    for(ll i=1;i<=top;i++){
        for(ll j=s[i];j<=s[i+1];j++){
            ll xx=(a[j]-a[s[i]])*(s[i+1]-s[i])-(a[s[i+1]]-a[s[i]])*(j-s[i]);
            if(xx<0) xx=-x;
            ll yy=s[i+1]-s[i];
            if(xx*y>x*yy) x=xx,y=yy;
        }
    }
    y*=2;
    ll g=__gcd(x,y);
    x/=g,y/=g;
    if(y==1) printf("%lld\n",x);
    else printf("%lld/%lld\n",x,y);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 229ms, 内存消耗: 4348K, 提交时间: 2018-07-07 22:41:10

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000005
ll x,y,g,u,v;
int n,i,j,a[MAXN],s[MAXN],t;
ll gcd(ll x,ll y)
{
	if(!y)return x;
	return gcd(y,x%y);
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	for(i=1;i<=n;i++)
	{
		while(t>1&&(ll)(a[i]-a[s[t]])*(s[t]-s[t-1])<=(ll)(a[s[t]]-a[s[t-1]])*(i-s[t]))t--;
		s[++t]=i;
	}
	x=0;
	y=1;
	for(i=1;i<t;i++)for(j=s[i];j<=s[i+1];j++)
	{
		u=(ll)(a[j]-a[s[i]])*(s[i+1]-s[i])-(ll)(a[s[i+1]]-a[s[i]])*(j-s[i]);
		if(u<0)u=-u;
		v=s[i+1]-s[i];
		if(u*y>x*v)
		{
			x=u;
			y=v;
		}
	}
	y*=2;
	g=gcd(x,y);
	x/=g;
	y/=g;
	if(y==1)cout<<x<<endl;
	else cout<<x<<'/'<<y<<endl;
	return 0;
}