Dada una array arr[] que consta de N enteros, la tarea es encontrar la diferencia absoluta entre la suma mínima y máxima de cualquier par de elementos (arr[i], arr[j]) tal que (i < j) y ( arr[i] < arr[j]) .
Ejemplos:
Entrada: arr[] = {1, 2, 4, 7}
Salida: 8
Explicación: Todos los pares posibles son:
- (1, 2) → Suma = 3
- (1, 4) → Suma = 5
- (1, 7) → Suma = 8
- (2, 4) → Suma = 6
- (2, 7) → Suma = 9
- (4, 7) → Suma = 11
Por lo tanto, la diferencia entre la suma máxima y mínima = 11 – 3 = 8.
Entrada: arr[] = {2, 5, 3}
Salida: 2
Enfoque: la idea para resolver el problema dado es crear dos arrays auxiliares para almacenar el mínimo y el máximo de sufijos de cada índice de sufijos de la array dada y luego encontrar la diferencia absoluta requerida.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos maxSum y minSum , para almacenar la suma máxima y mínima de un par de elementos de la array dada de acuerdo con las condiciones dadas.
- Inicialice dos arrays, digamos suffixMax[] y suffixMin[] de tamaño N , para almacenar el máximo y el mínimo de sufijos para cada índice de la array arr[] .
- Recorra la array dada arr[] al revés y actualice suffixMin[] y suffixMax[] en cada índice.
- Ahora, itere sobre el rango [0, N – 1] y realice los siguientes pasos:
- Si el elemento actual arr[i] es menor que suffixMax[i] , actualice el valor de maxSum como el máximo de maxSum y (arr[i] + suffixMax[i]) .
- Si el elemento actual arr[i] es menor que suffixMin[i] , actualice el valor de minSum como el mínimo de minSum y (arr[i] + suffixMin[i]) .
- Después de completar los pasos anteriores, imprima el valor (maxSum – minSum) como la diferencia resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the difference between
// the maximum and minimum sum of a pair
// (arr[i], arr[j]) from the array such
// that i < j and arr[i] < arr[j]
int GetDiff(int A[], int N)
{
// Stores the maximum from
// the suffix of the array
int SuffMaxArr[N];
// Set the last element
SuffMaxArr[N - 1] = A[N - 1];
// Traverse the remaining array
for (int i = N - 2; i >= 0; --i) {
// Update the maximum from suffix
// for the remaining indices
SuffMaxArr[i] = max(SuffMaxArr[i + 1],
A[i + 1]);
}
// Stores the maximum sum of any pair
int MaximumSum = INT_MIN;
// Calculate the maximum sum
for (int i = 0; i < N - 1; i++) {
if (A[i] < SuffMaxArr[i])
MaximumSum
= max(MaximumSum,
A[i] + SuffMaxArr[i]);
}
// Stores the maximum sum of any pair
int MinimumSum = INT_MAX;
// Stores the minimum of suffixes
// from the given array
int SuffMinArr[N];
// Set the last element
SuffMinArr[N - 1] = INT_MAX;
// Traverse the remaining array
for (int i = N - 2; i >= 0; --i) {
// Update the maximum from suffix
// for the remaining indices
SuffMinArr[i] = min(SuffMinArr[i + 1],
A[i + 1]);
}
// Calculate the minimum sum
for (int i = 0; i < N - 1; i++) {
if (A[i] < SuffMinArr[i]) {
MinimumSum = min(MinimumSum,
A[i] + SuffMinArr[i]);
}
}
// Return the resultant difference
return abs(MaximumSum - MinimumSum);
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 1, 3, 7, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << GetDiff(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the difference between
// the maximum and minimum sum of a pair
// (arr[i], arr[j]) from the array such
// that i < j and arr[i] < arr[j]
static int GetDiff(int A[], int N)
{
// Stores the maximum from
// the suffix of the array
int SuffMaxArr[] = new int[N];
// Set the last element
SuffMaxArr[N - 1] = A[N - 1];
// Traverse the remaining array
for(int i = N - 2; i >= 0; --i)
{
// Update the maximum from suffix
// for the remaining indices
SuffMaxArr[i] = Math.max(SuffMaxArr[i + 1],
A[i + 1]);
}
// Stores the maximum sum of any pair
int MaximumSum = Integer.MIN_VALUE;
// Calculate the maximum sum
for(int i = 0; i < N - 1; i++)
{
if (A[i] < SuffMaxArr[i])
MaximumSum = Math.max(MaximumSum,
A[i] + SuffMaxArr[i]);
}
// Stores the maximum sum of any pair
int MinimumSum = Integer.MAX_VALUE;
// Stores the minimum of suffixes
// from the given array
int SuffMinArr[] = new int[N];
// Set the last element
SuffMinArr[N - 1] = Integer.MAX_VALUE;
// Traverse the remaining array
for(int i = N - 2; i >= 0; --i)
{
// Update the maximum from suffix
// for the remaining indices
SuffMinArr[i] = Math.min(SuffMinArr[i + 1],
A[i + 1]);
}
// Calculate the minimum sum
for(int i = 0; i < N - 1; i++)
{
if (A[i] < SuffMinArr[i])
{
MinimumSum = Math.min(MinimumSum,
A[i] + SuffMinArr[i]);
}
}
// Return the resultant difference
return Math.abs(MaximumSum - MinimumSum);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 4, 1, 3, 7, 5, 6 };
int N = arr.length;
// Function Call
System.out.println(GetDiff(arr, N));
}
}
// This code is contributed by Kingash
Python3
# Python 3 program for the above approach import sys # Function to find the difference between # the maximum and minimum sum of a pair # (arr[i], arr[j]) from the array such # that i < j and arr[i] < arr[j] def GetDiff(A, N): # Stores the maximum from # the suffix of the array SuffMaxArr = [0 for i in range(N)] # Set the last element SuffMaxArr[N - 1] = A[N - 1] # Traverse the remaining array i = N-2 while(i >= 0): # Update the maximum from suffix # for the remaining indices SuffMaxArr[i] = max(SuffMaxArr[i + 1], A[i + 1]) i -= 1 # Stores the maximum sum of any pair MaximumSum = -sys.maxsize-1 # Calculate the maximum sum for i in range(N-1): if (A[i] < SuffMaxArr[i]): MaximumSum = max(MaximumSum, A[i] + SuffMaxArr[i]) # Stores the maximum sum of any pair MinimumSum = sys.maxsize # Stores the minimum of suffixes # from the given array SuffMinArr = [0 for i in range(N)] # Set the last element SuffMinArr[N - 1] = sys.maxsize # Traverse the remaining array i = N-2 while(i >= 0): # Update the maximum from suffix # for the remaining indices SuffMinArr[i] = min(SuffMinArr[i + 1], A[i + 1]) i -= 1 # Calculate the minimum sum for i in range(N - 1): if (A[i] < SuffMinArr[i]): MinimumSum = min(MinimumSum,A[i] + SuffMinArr[i]) # Return the resultant difference return abs(MaximumSum - MinimumSum) # Driver Code if __name__ == '__main__': arr = [2, 4, 1, 3, 7, 5, 6] N = len(arr) # Function Call print(GetDiff(arr, N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# Program to implement
// the above approach
using System;
class GFG
{
// Function to find the difference between
// the maximum and minimum sum of a pair
// (arr[i], arr[j]) from the array such
// that i < j and arr[i] < arr[j]
static int GetDiff(int[] A, int N)
{
// Stores the maximum from
// the suffix of the array
int[] SuffMaxArr = new int[N];
// Set the last element
SuffMaxArr[N - 1] = A[N - 1];
// Traverse the remaining array
for(int i = N - 2; i >= 0; --i)
{
// Update the maximum from suffix
// for the remaining indices
SuffMaxArr[i] = Math.Max(SuffMaxArr[i + 1],
A[i + 1]);
}
// Stores the maximum sum of any pair
int MaximumSum = Int32.MinValue;
// Calculate the maximum sum
for(int i = 0; i < N - 1; i++)
{
if (A[i] < SuffMaxArr[i])
MaximumSum = Math.Max(MaximumSum,
A[i] + SuffMaxArr[i]);
}
// Stores the maximum sum of any pair
int MinimumSum = Int32.MaxValue;
// Stores the minimum of suffixes
// from the given array
int[] SuffMinArr = new int[N];
// Set the last element
SuffMinArr[N - 1] = Int32.MaxValue;
// Traverse the remaining array
for(int i = N - 2; i >= 0; --i)
{
// Update the maximum from suffix
// for the remaining indices
SuffMinArr[i] = Math.Min(SuffMinArr[i + 1],
A[i + 1]);
}
// Calculate the minimum sum
for(int i = 0; i < N - 1; i++)
{
if (A[i] < SuffMinArr[i])
{
MinimumSum = Math.Min(MinimumSum,
A[i] + SuffMinArr[i]);
}
}
// Return the resultant difference
return Math.Abs(MaximumSum - MinimumSum);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 2, 4, 1, 3, 7, 5, 6 };
int N = arr.Length;
// Function Call
Console.WriteLine(GetDiff(arr, N));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the difference between
// the maximum and minimum sum of a pair
// (arr[i], arr[j]) from the array such
// that i < j and arr[i] < arr[j]
function GetDiff(A, N)
{
// Stores the maximum from
// the suffix of the array
let SuffMaxArr = Array(N).fill(0);
// Set the last element
SuffMaxArr[N - 1] = A[N - 1];
// Traverse the remaining array
for(let i = N - 2; i >= 0; --i)
{
// Update the maximum from suffix
// for the remaining indices
SuffMaxArr[i] = Math.max(SuffMaxArr[i + 1],
A[i + 1]);
}
// Stores the maximum sum of any pair
let MaximumSum = Number.MIN_VALUE;
// Calculate the maximum sum
for(let i = 0; i < N - 1; i++)
{
if (A[i] < SuffMaxArr[i])
MaximumSum = Math.max(MaximumSum,
A[i] + SuffMaxArr[i]);
}
// Stores the maximum sum of any pair
let MinimumSum = Number.MAX_VALUE;
// Stores the minimum of suffixes
// from the given array
let SuffMinArr = Array(N).fill(0);
// Set the last element
SuffMinArr[N - 1] = Number.MAX_VALUE;
// Traverse the remaining array
for(let i = N - 2; i >= 0; --i)
{
// Update the maximum from suffix
// for the remaining indices
SuffMinArr[i] = Math.min(SuffMinArr[i + 1],
A[i + 1]);
}
// Calculate the minimum sum
for(let i = 0; i < N - 1; i++)
{
if (A[i] < SuffMinArr[i])
{
MinimumSum = Math.min(MinimumSum,
A[i] + SuffMinArr[i]);
}
}
// Return the resultant difference
return Math.abs(MaximumSum - MinimumSum);
}
// Driver Code
let arr = [ 2, 4, 1, 3, 7, 5, 6 ];
let N = arr.length;
// Function Call
document.write(GetDiff(arr, N));
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA