题目描述
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
代码语言：javascript复制4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328输出 #1
代码语言：javascript复制12
6
4761
381274500335分析
假设我们有两个相邻的数 a,b,(alt b)，显然对于这个长度为 2 的序列的解是 acdot b。现在我们向 b 后面添加一个数 c，对于这个序列的解改变当且仅当两种情况：
- 第一种情况，当 blt c 时，解为 acdot c
- 第二种情况，当 agt c 时，解为 bcdot c
对于第一种情况，显然 bcdot cgt acdot c，所以我们将 a 移出序列可以得到更优解；对于第二种情况，显然解与 a 无关。综上，我们只需要考虑序列长度为 2 的情况，因此我们只需要对所有数依次判断更新答案即可。
记得开long long ，时间复杂度 O(n)
代码
代码语言：javascript复制#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("%lldn",ans);
}
}最后修改：2021 年 08 月 04 日 11 : 26 AM
© 允许规范转载
