PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ishan Khandelwal
Preparer: Souradeep Paul
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh
DIFFICULTY:
1375
PREREQUISITES:
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! */
import java.io.BufferedReader;
import java.io.InputStreamReader;
/* 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
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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;
n = Integer.parseInt(br.readLine());
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
so max(minmin,maxmin) is the max
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[0]);
ll max = abs(arr[0]);
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[0]);
ll max1 = (arr[0]);
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
Your Output
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();
}
}
}