题目描述

小明国庆节来北京玩，北京有N个景点，第 i 个景点的评分用a[i]表示，两个景点i, j之间的距离为j - i(j > i)。

小明一天只能游玩两个景点，我们认为总评分是两个景点的评分之和减去两个景点之间的距离，即为a[i]+a[j]+i-j。

那么小明选择哪两个景点才会总评分最大呢？

输入格式
第一行包含整数N。

第二行分别输入N个景点的评分。

输出格式
输出最大评分

数据范围
2≤N≤105,
1≤a[i]≤1000

输入样例

5
11 6 5 18 12

输出样例

29

算法1

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

直接暴力枚举 TLE

C++ 代码

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

const int N = 100010;

int a[ N ];

int n;


int main()
{
    scanf( "%d", &n );
    for( int i = 1; i <= n; i ++ ) scanf( "%d", &a[ i ] );
    int res = INT_MIN;
    for( int j = 1; j <= n; j ++ )
    {
        int t = INT_MIN;
        for( int i = 1; i < j; i ++ )
        {
            t = max( t, a[ i ] + i + a[ j ] - j );
        }
        res = max( res, t );
    }
    printf( "%d\n", res );
    return 0;
}

算法2

(维护最大值) $O(n)$

观察算法1的代码，可以用一个变量维护a[ i ] + i的最大值。
省去一重循环

C++ 代码

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

const int N = 100010;

int a[ N ];

int n;

int main()
{
    scanf( "%d", &n );
    for( int i = 1; i <= n; i ++ ) scanf( "%d", &a[ i ] );
    int res = INT_MIN;
    int max_Q = a[ 1 ] + 1;
    for( int j = 2; j <= n; j ++ )
    {
        res = max( res, max_Q + a[ j ] - j );
        max_Q = max( max_Q, a[ j ] + j );
    }
    printf( "%d\n", res );
    return 0;
}

算法3

(线段树) $O(nlog(n))$

计算公式为 a[ i ] + i + a[ j ] - j( j > i );

对于每个i，求区间[ i + 1, N ]中的a[ x ] - x ( x 属于区间[ i + 1, N ] )的最大值。可以用线段树进行维护

C++ 代码

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

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

const int maxn = 100010;

int N;
pair< int, int > p[ maxn ];

int Max[ maxn << 2 ];

void Pushup( int rt )
{
    Max[ rt ] = max( Max[ rt << 1 ], Max[ rt << 1 | 1 ] );
}

void build( int l, int r, int rt )
{
    if( l == r )
    {
        Max[ rt ] = p[ l ].second - p[ l ].first;
        return;
    }
    auto m = l + r >> 1;
    build( lson );
    build( rson );
    Pushup( rt );
}

int query( int L, int R, int l, int r, int rt )
{
    if( L <= l && R >= r ) return Max[ rt ];
    auto m = l + r >> 1;
    int vl = INT_MIN;
    int vr = INT_MIN;
    if( L <= m ) vl = query( L, R, lson );
    if( R > m )  vr = query( L, R, rson );
    return max( vl, vr );
}

int main()
{
    scanf( "%d", &N );
    for( int i = 1; i <= N; i ++ )
    {
        scanf( "%d", &p[ i ].second );
        p[ i ].first = i;
    }
    build( 1, N, 1 );
    int goal = INT_MIN;
    for( int i = 1; i < N ; i ++ )
    {
        goal = max( goal, p[ i ].first + p[ i ].second + query( i + 1, N, 1, N, 1 ) );
    }
    printf( "%d\n", goal );
    return 0;
}