Codeforcess Solution 1554-A A. Cherry ,C++, Java, Js and Python

Algorithm

You are given $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ . Find the maximum value of $m a x (a_{l}, a_{l + 1}, \dots, a_{r}) \cdot m i n (a_{l}, a_{l + 1}, \dots, a_{r})$ over all pairs $(l, r)$ of integers for which $1 \leq l < r \leq n$ .

Input

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

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

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{6}$ ).

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

Output

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

Example
input
Copy
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328
output
Copy
12
6
4761
381274500335

Note

Let $f (l, r) = m a x (a_{l}, a_{l + 1}, \dots, a_{r}) \cdot m i n (a_{l}, a_{l + 1}, \dots, a_{r})$ .

In the first test case,

$f (1, 2) = m a x (a_{1}, a_{2}) \cdot m i n (a_{1}, a_{2}) = m a x (2, 4) \cdot m i n (2, 4) = 4 \cdot 2 = 8$ .
$f (1, 3) = m a x (a_{1}, a_{2}, a_{3}) \cdot m i n (a_{1}, a_{2}, a_{3}) = m a x (2, 4, 3) \cdot m i n (2, 4, 3) = 4 \cdot 2 = 8$ .
$f (2, 3) = m a x (a_{2}, a_{3}) \cdot m i n (a_{2}, a_{3}) = m a x (4, 3) \cdot m i n (4, 3) = 4 \cdot 3 = 12$ .

So the maximum is $f (2, 3) = 12$ .

In the second test case, the maximum is $f (1, 2) = f (1, 3) = f (2, 3) = 6$ .

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

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


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  ll n;
  while(t--){
    cin>n;
    ll a, b, c, max = -1;
    cin>>a;
    for(ll i = 1; i < n; i++){
      cin>>b;
      c = a * b;
      max = (c > max) ? c : max;
      a = b;
    }
    cout<<max<<endl;
  }

}

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

12
6
4761
381274500335

Demonstration

Codeforcess Solution 1554-A A. Cherry ,C++, Java, Js and Python,1554-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 459 0