题目描述

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
如果觉得我的文章对你有用,请随意赞赏