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.
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328
12
6
4761
381274500335
假设我们有两个相邻的数 a,b\,(a\lt b),显然对于这个长度为 2 的序列的解是 a\cdot b。现在我们向 b 后面添加一个数 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
© 允许规范转载