 # SUBARRY - Editorial

Author: Ishan Khandelwal
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh

1375

Observation

# PROBLEM:

The interesting value of an array is defined to be the product of its maximum and minimum elements.
Given an array A, find the maximum and minimum interesting values across all its subarrays.

# EXPLANATION:

Let mn be the minimum element of A, and mx be its maximum element.

Then, the minimum possible interesting value is \min(mn^2, mx^2, mn\cdot mx) and the maximum is \max(mn^2, mx^2).

Proof

This can be proved by casework on the types of elements in A.

• Suppose all the elements of A are \geq 0. Then, the minimum possible value is obviously mn^2 and the maximum is mx^2, both obtained by choosing the subarray consisting of that single element.
• Suppose all the elements of A are \leq 0. Then, the minimum value is mx^2 and the maximum value is mn^2, once again obtained by choosing appropriate subarrays of size 1.
• Now, suppose A has both positive and negative elements. This means that mn \lt 0 and mx \gt 0.
• The maximum is whichever is larger among mn^2 and mx^2
• The minimum is mn\cdot mx.

All these can be implemented as separate cases, or the symmetry between them can be used to form the expressions \min(mn^2, mx^2, mn\cdot mx) and \max(mn^2, mx^2) as noted above.

# TIME COMPLEXITY

\mathcal{O}(N) or per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mn, mx = min(a), max(a)
print(min(mn*mn, mn*mx, mx*mx), max(mn*mn, mx*mx))

1 Like

/* package codechef; // don’t place package name! */

/* Name of the class has to be “Main” only if the class is public. */
class Main {

public static void main(String[] args) throws java.lang.Exception {
// your code goes here
int t = Integer.parseInt(br.readLine());
int n = 0, vals[] = null;
String data[] = null;
long min = 0l, max = 0l, aux = 0l, minR = 0l, maxR = 0l;
for (int i = 0; i < t; i++) {
min = Long.MAX_VALUE;
max = Long.MIN_VALUE;
data = br.readLine().split(" ");

for (int j = 0; j < n; j++) {
aux = Long.parseLong(data[j]);
if (max < aux) {
max = aux;
}
if (min > aux) {
min = aux;
}
}

if (min == max) {
minR = min * min;
maxR = max * max;
System.out.println(minR + " " + maxR);
continue;
}

if (max < 0) {
minR = max * max;
maxR = min * min;
System.out.println(minR + " " + maxR);
continue;
}
if (max == 0) {
minR = 0;
maxR = min * min;
System.out.println(minR + " " + maxR);
continue;
}

if (min < 0 && max > 0) {
minR = min * max;
maxR = max * max;
System.out.println(minR + " " + maxR);
continue;
}
if (min == 0) {
minR = min * min;
maxR = max * max;
System.out.println(minR + " " + maxR);
}

}
}


# }

why is this failing

assign first value of array to them. Instead of min and max

Thank you apoorv_2204 but logically it is correct and getting min and max

1 Like

maxR can also be min * min, for example consider the case where A = [-2, 1].

2 Likes

Correct

so max(minmin,maxmin) is the max

Thanks iceknight1093

WHY IS MY CODE FAILING? IT IS GIVING CORRECT ANSWER FOR ALL THE CASES MENTIONED ABOVE

#include<iostream>
#include<vector>
#include<numeric>
#include<bits/stdc++.h>

#define ll long long
#define l long

using namespace std;

void getSolution(){
ll n;
cin>>n;
ll arr[n];
for (ll i = 0; i < n; i++)
{
cin>>arr[i];
}
ll min = abs(arr);
ll max = abs(arr);
for (ll i = 1; i < n; i++)
{
if(abs(arr[i]) < min){
min = abs(arr[i]);
}
if(abs(arr[i]) > max){
max = abs(arr[i]);
}
}
ll k = min*max;
if(min*min < min*max){
k = min;
}
ll min1 = (arr);
ll max1 = (arr);
for (ll i = 1; i < n; i++)
{
if((arr[i]) < min1){
min1 = (arr[i]);
}
if((arr[i]) > max1){
max1 = (arr[i]);
}
}
if(min1*max1<k){
k = min1 * max1;
}
cout<<k<<" "<<max*max<<endl;
}

int main() {
// your code goes here
int t;
cin>>t;
while(t--){
getSolution();
}
return 0;
}


Try this test case:
Input

1
3
-7 -3 -5


Expected Output

9 49


3 49


Yes, I got my mistake. Thanks

Java Code Accepted

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);

int t = sc.nextInt();

while(t-- > 0)
{
int n = sc.nextInt();

long min = Long.MAX_VALUE;
long max = Long.MIN_VALUE;

for(int i=0; i<n; i++)
{
long a = sc.nextLong();

min = Math.min(min,a);
max = Math.max(max,a);
}

long maxx = Math.max((min*min), (max*max));         // negative * negative = positive
long minn = min;

if(min < 0 && max >= 0)
{
minn = min* max;
}
else if(min<0 && max <0)
{
minn = max*max;
}
else
{
minn = min*min;
}

System.out.print(minn + " " + maxx);

System.out.println();
}
}
}