Dada una array arr[] que consta de N enteros, la tarea es dividir la array en subarreglos de modo que la suma de la diferencia entre los elementos máximo y mínimo para todos los subarreglos sea máxima.
Ejemplos :
Entrada: arr[] = {8, 1, 7, 9, 2}
Salida: 14
Explicación:
Considere dividir la array dada en subarreglos como {8, 1} y {7, 9, 2}. Ahora, la diferencia entre los elementos máximo y mínimo son:
- {8, 1}: la diferencia es (8 – 1) = 7.
- {7, 9, 2}: La diferencia es (9 – 2) = 7.
Por lo tanto, la suma de la diferencia es 7 + 7 = 14.
Entrada: arr[] = {1, 2, 1, 0, 5}
Salida: 6
Enfoque: El problema dado se puede resolver usando Programación Dinámica . Siga los pasos para resolver el problema:
- Inicialice una array, digamos dp[] , donde dp[i] representa la suma máxima de la diferencia entre el elemento máximo y mínimo para todo el subarreglo para el primer elemento de la array i .
- Inicialice dp[0] como 0 .
- Recorra la array dada sobre el rango [1, N – 1] y realice los siguientes pasos:
- Inicialice una variable, digamos min como arr[i] , que almacene el elemento mínimo sobre el rango [0, i] .
- Inicialice una variable, digamos max como arr[i] , que almacene el elemento máximo sobre el rango [0, i] .
- Iterar sobre el rango [0, i] usando la variable j en el orden inverso y realizar los siguientes pasos:
- Actualice el valor de min como el mínimo de min y arr[j] .
- Actualice el valor de max como el mínimo de max y arr[j] .
- Actualice el valor de dp[j] al máximo de dp[j] y (max – min + dp[i]) .
- Después de completar los pasos anteriores, imprima el valor de dp[N – 1] como resultado.
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 maximum sum of
// difference between maximums and
// minimums in the splitted subarrays
int getValue(int arr[], int N)
{
int dp[N];
memset(dp, 0, sizeof(dp));
// Base Case
dp[0] = 0;
// Traverse the array
for(int i = 1; i < N; i++)
{
// Stores the maximum and
// minimum elements upto
// the i-th index
int minn = arr[i];
int maxx = arr[i];
// Traverse the range [0, i]
for(int j = i; j >= 0; j--)
{
// Update the minimum
minn = min(arr[j], minn);
// Update the maximum
maxx = max(arr[j], maxx);
// Update dp[i]
dp[i] = max(dp[i], maxx - minn +
((j >= 1) ? dp[j - 1] : 0));
}
}
// Return the maximum
// sum of difference
return dp[N - 1];
}
// Driver code
int main()
{
int arr[] = { 8, 1, 7, 9, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << getValue(arr, N);
return 0;
}
// This code is contributed by Kingash
Java
// Java program for the above approach
import java.util.*;
public class Main {
// Function to find maximum sum of
// difference between maximums and
// minimums in the splitted subarrays
static int getValue(int[] arr, int N)
{
int dp[] = new int[N];
// Base Case
dp[0] = 0;
// Traverse the array
for (int i = 1; i < N; i++) {
// Stores the maximum and
// minimum elements upto
// the i-th index
int min = arr[i];
int max = arr[i];
// Traverse the range [0, i]
for (int j = i; j >= 0; j--) {
// Update the minimum
min = Math.min(arr[j], min);
// Update the maximum
max = Math.max(arr[j], max);
// Update dp[i]
dp[i] = Math.max(
dp[i],
max - min + ((j >= 1)
? dp[j - 1]
: 0));
}
}
// Return the maximum
// sum of difference
return dp[N - 1];
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 8, 1, 7, 9, 2 };
int N = arr.length;
System.out.println(getValue(arr, N));
}
}
C#
// C# program for the above approach
using System;
class GFG{
// Function to find maximum sum of
// difference between maximums and
// minimums in the splitted subarrays
static int getValue(int[] arr, int N)
{
int[] dp = new int[N];
// Base Case
dp[0] = 0;
// Traverse the array
for(int i = 1; i < N; i++)
{
// Stores the maximum and
// minimum elements upto
// the i-th index
int min = arr[i];
int max = arr[i];
// Traverse the range [0, i]
for(int j = i; j >= 0; j--)
{
// Update the minimum
min = Math.Min(arr[j], min);
// Update the maximum
max = Math.Max(arr[j], max);
// Update dp[i]
dp[i] = Math.Max(
dp[i],
max - min + ((j >= 1) ?
dp[j - 1] : 0));
}
}
// Return the maximum
// sum of difference
return dp[N - 1];
}
// Driver Code
static public void Main()
{
int[] arr = { 8, 1, 7, 9, 2 };
int N = arr.Length;
Console.Write(getValue(arr, N));
}
}
// This code is contributed by code_hunt
Python3
# python 3 program for the above approach # Function to find maximum sum of # difference between maximums and # minimums in the splitted subarrays def getValue(arr, N): dp = [0 for i in range(N)] # Traverse the array for i in range(1, N): # Stores the maximum and # minimum elements upto # the i-th index minn = arr[i] maxx = arr[i] j = i # Traverse the range [0, i] while(j >= 0): # Update the minimum minn = min(arr[j], minn) # Update the maximum maxx = max(arr[j], maxx) # Update dp[i] dp[i] = max(dp[i], maxx - minn + (dp[j - 1] if (j >= 1) else 0)) j -= 1 # Return the maximum # sum of difference return dp[N - 1] # Driver code if __name__ == '__main__': arr = [8, 1, 7, 9, 2] N = len(arr) print(getValue(arr, N)) # This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find maximum sum of
// difference between maximums and
// minimums in the splitted subarrays
function getValue(arr, N)
{
let dp = Array.from({length: N}, (_, i) => 0);
// Base Case
dp[0] = 0;
// Traverse the array
for (let i = 1; i < N; i++) {
// Stores the maximum and
// minimum elements upto
// the i-th index
let min = arr[i];
let max = arr[i];
// Traverse the range [0, i]
for (let j = i; j >= 0; j--) {
// Update the minimum
min = Math.min(arr[j], min);
// Update the maximum
max = Math.max(arr[j], max);
// Update dp[i]
dp[i] = Math.max(
dp[i],
max - min + ((j >= 1)
? dp[j - 1]
: 0));
}
}
// Return the maximum
// sum of difference
return dp[N - 1];
}
// Driver code
let arr = [ 8, 1, 7, 9, 2 ];
let N = arr.length;
document.write(getValue(arr, N));
</script>
Producción:
14
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA