【题解】Cherry

题目描述

You are given n integers a_1, a_2, \ldots, a_n . Find the maximum value of max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r) over all pairs (l, r) of integers for which 1 \le l < r \le n

输入格式

The first line contains a single integer t ( 1 \le t \le 10\,000 ) — the number of test cases.

The first line of each test case contains a single integer n ( 2 \le n \le 10^5 ).

The second line of each test case contains n integers a_1, a_2, \ldots, a_n ( 1 \le a_i \le 10^6 ).

It is guaranteed that the sum of n over all test cases doesn't exceed 3 \cdot 10^5 .

输出格式

For each test case, print a single integer — the maximum possible value of the product from the statement.

输入输出样例

输入 #1

4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

输出 #1

12
6
4761
381274500335

分析

假设我们有两个相邻的数 a,b\,(a\lt b)，显然对于这个长度为 2 的序列的解是 a\cdot b。现在我们向 b 后面添加一个数 c，对于这个序列的解改变当且仅当两种情况：

• 第一种情况，当 b\lt c 时，解为 a\cdot c
• 第二种情况，当 a\gt c 时，解为 b\cdot c

对于第一种情况，显然 b\cdot c\gt a\cdot c，所以我们将 a 移出序列可以得到更优解；对于第二种情况，显然解与 a 无关。综上，我们只需要考虑序列长度为 2 的情况，因此我们只需要对所有数依次判断更新答案即可。

记得开long long ，时间复杂度 O(n)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n;
int ans;
int a[100001];
signed main(){
    scanf("%lld",&t);
    while(t--){
        memset(a,0,sizeof(a));
        ans=0;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++){
            ans=max(ans,a[i]*a[i+1]);
        }
        printf("%lld\n",ans);
    }
}

最后修改：2021 年 08 月 04 日 11 : 26 AM

© 允许规范转载