Header Ads Widget

Max difference | hackerearth solution

Rajnish Tripathi 21:48
Problem

The weight of an array is defined as the difference between the maximum and minimum element of the array. For example, the weight of the array [3, 7, 1, 2] is (7 - 1) = 6, the weight of the array [2] is (2 - 2) = 0, the weight of an empty array is 0.
You are given an array A of length N. You have to divide the elements of A into two subsequences S1, and S2 (one of S1, S2 can be empty) such that:

  • Each element of A belongs to one of S1 and S2.
  • The sum of weights of the two subsequences is maximum.

Find the maximum possible sum of weights of the two subsequences.

 Input format

  • The first line contains T denoting the number of test cases. The description of T test cases is as follows:
  • For each test case:
    • The first line contains N denoting the size of array A.
    • The second line contains N space-separated integers A[1], A[2], ....., A[N] - denoting the elements of A.

Output format
For each test case, print the maximum possible sum of weights of the two subsequences.

Constraints

1≤�≤1042≤�≤1051≤��≤109�����������������������������������2⋅105.

 

Sample Input
1
3
1 2 3
Sample Output
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Test case 1: One possible division is [1, 3], [2] Here the total weight is = (3 - 1) + (2 - 2) = 2..  

Code(C++):-

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll T,i,N;
cin>>T;
while(T--) {
cin>>N;
ll ar[N],min_ind = 0, max_ind = 0, maxm = -1, minm = INT_MAX, ans = 0;
for(i = 0; i < N; i++) {
cin>>ar[i];
if (ar[i] > maxm) {
maxm = ar[i];
max_ind = i;
}
if (ar[i] < minm) {
minm = ar[i];
min_ind = i;
}
}
ans += (maxm - minm);
maxm = -1, minm = INT_MAX;
for (i = 0; i < N; i++) {
if (i != min_ind && i != max_ind) {
maxm = max(maxm, ar[i]);
minm = min(minm, ar[i]);
}
}
if (maxm != -1 && minm != INT_MAX) {
ans += (maxm - minm);
}
cout<<ans<<"\n";
}
return 0;
}

Code(JAVA):-

import java.io.*;
import java.util.*;
public class TestClass {
public static void main(String args[] ) throws Exception {
FastReader fs = new FastReader();
int T = fs.nextInt();
for(int t = 0;t<T;t++){
int N = fs.nextInt();
int A[] = new int[N];
for(int i=0;i<N;i++)
A[i] = fs.nextInt();
System.out.println(maxWeight(A, N));
}
fs.close();
}
static int maxWeight(int A[], int N){
if(N<=1) return 0;
int min1 = Integer.MAX_VALUE;
int minp1 = -1;
int max1 = Integer.MIN_VALUE;
int maxp1 = -1;
for(int i = 0; i<N;i++){
if(min1>A[i]){
min1 = A[i];
minp1 = i;
}
if(max1<A[i]){
max1 = A[i];
maxp1 = i;
}
}
int min2 = Integer.MAX_VALUE;
int minp2 = -1;
int max2 = Integer.MIN_VALUE;
int maxp2 = -1;
for(int i = 0; i<N;i++){
if(i==minp1 || i == maxp1) continue;
if(min2>A[i]){
min2 = A[i];
minp2 = i;
}
if(max2<A[i]){
max2 = A[i];
maxp2 = i;
}
}
if(N==2){
min2 = 0;
max2 = 0;
}
return (max1-min1) + (max2-min2);
}
static class FastReader{
BufferedReader br;
StringTokenizer st;
FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
int nextInt(){
while(st==null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
} catch(IOException e){
e.printStackTrace();
}
}
return Integer.parseInt(st.nextToken());
}
void close(){
try{
br.close();
}catch(IOException e){
e.printStackTrace();
}
}
    }
}



Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments