Dada una array arr[] que consta de N enteros, la tarea es maximizar la suma de la diferencia del máximo y el mínimo en cada subarreglo dividiendo la array dada en subarreglos que no se superponen.
Ejemplos:
Entrada: arr[] = {8, 1, 7, 9, 2}
Salida: 14
Explicación:
Divida la array dada arr[] como {8, 1}, {7, 9, 2}. Ahora, la suma de la diferencia máxima y mínima para todos los subarreglos es (8 – 7) + (9 – 2) = 7 + 7 = 14, que es la máxima entre todas las combinaciones posibles.Entrada: arr[] = {1, 2, 1, 0, 5}
Salida: 6
Enfoque: el problema dado se puede resolver considerando todas las posibles rupturas de subarreglos y encontrar la suma de la diferencia del máximo y mínimo en cada subarreglo y maximizar este valor. Esta idea se puede implementar usando Programación Dinámica . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array, dp[] con todos los elementos como 0 , de modo que dp[i] almacene la suma de todas las divisiones posibles de los primeros i elementos, de modo que la suma de la diferencia del máximo y el mínimo en cada subarreglo sea máxima.
- Recorra la array dada arr[] usando la variable i y realice los siguientes pasos:
- Elija el valor actual como el elemento máximo y mínimo para los subarreglos y guárdelo en variables, digamos minValue y maxValue respectivamente.
- Iterar un ciclo sobre el rango [0, i] usando la variable j y realizar los siguientes pasos:
- Actualice minValue y maxValue con el elemento de array arr[j] .
- Si el valor de j es positivo, actualice dp[i] como el máximo de dp[i] y (maxValue – minValue + dp[j – 1]) . De lo contrario, actualice dp[i] como el máximo de dp[i] y (maxValue – minValue) .
- Después de completar los pasos anteriores, imprima el valor de dp[N – 1] como el valor máximo 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 maximum sum of
// differences of subarrays by splitting
// array into non-overlapping subarrays
int maxDiffSum(int arr[], int n)
{
// Stores the answer for prefix
// and initialize with zero
int dp[n];
memset(dp, 0, sizeof(dp));
// Assume i-th index as right endpoint
for (int i = 0; i < n; i++) {
// Choose the current value as
// the maximum and minimum
int maxVal = arr[i], minVal = arr[i];
// Find the left endpoint and
// update the array dp[]
for (int j = i; j >= 0; j--) {
minVal = min(minVal, arr[j]);
maxVal = max(maxVal, arr[j]);
if (j - 1 >= 0)
dp[i] = max(
dp[i], maxVal - minVal + dp[j - 1]);
else
dp[i] = max(
dp[i], maxVal - minVal);
}
}
// Return answer
return dp[n - 1];
}
// Driver Code
int main()
{
int arr[] = { 8, 1, 7, 9, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxDiffSum(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the maximum sum of
// differences of subarrays by splitting
// array into non-overlapping subarrays
static int maxDiffSum(int[] arr, int n)
{
// Stores the answer for prefix
// and initialize with zero
int[] dp = new int[n];
// Assume i-th index as right endpoint
for (int i = 0; i < n; i++) {
// Choose the current value as
// the maximum and minimum
int maxVal = arr[i], minVal = arr[i];
// Find the left endpoint and
// update the array dp[]
for (int j = i; j >= 0; j--) {
minVal = Math.min(minVal, arr[j]);
maxVal = Math.max(maxVal, arr[j]);
if (j - 1 >= 0)
dp[i] = Math.max(
dp[i], maxVal - minVal + dp[j - 1]);
else
dp[i]
= Math.max(dp[i], maxVal - minVal);
}
}
// Return answer
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.print(maxDiffSum(arr, N));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python Program to implement # the above approach # Function to find the maximum sum of # differences of subarrays by splitting # array into non-overlapping subarrays def maxDiffSum(arr, n): # Stores the answer for prefix # and initialize with zero dp = [0] * n # Assume i-th index as right endpoint for i in range(n): # Choose the current value as # the maximum and minimum maxVal = arr[i] minVal = arr[i] # Find the left endpoint and # update the array dp[] for j in range(i, -1, -1): minVal = min(minVal, arr[j]) maxVal = max(maxVal, arr[j]) if (j - 1 >= 0): dp[i] = max( dp[i], maxVal - minVal + dp[j - 1]) else: dp[i] = max( dp[i], maxVal - minVal) # Return answer return dp[n - 1] # Driver Code arr = [8, 1, 7, 9, 2] N = len(arr) print(maxDiffSum(arr, N)) # This code is contributed by _saurabh_jaiswal
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the maximum sum of
// differences of subarrays by splitting
// array into non-overlapping subarrays
static int maxDiffSum(int[] arr, int n)
{
// Stores the answer for prefix
// and initialize with zero
int[] dp = new int[n];
// Assume i-th index as right endpoint
for (int i = 0; i < n; i++) {
// Choose the current value as
// the maximum and minimum
int maxVal = arr[i], minVal = arr[i];
// Find the left endpoint and
// update the array dp[]
for (int j = i; j >= 0; j--) {
minVal = Math.Min(minVal, arr[j]);
maxVal = Math.Max(maxVal, arr[j]);
if (j - 1 >= 0)
dp[i] = Math.Max(
dp[i], maxVal - minVal + dp[j - 1]);
else
dp[i]
= Math.Max(dp[i], maxVal - minVal);
}
}
// Return answer
return dp[n - 1];
}
// Driver Code
public static void Main()
{
int[] arr = { 8, 1, 7, 9, 2 };
int N = arr.Length;
Console.WriteLine(maxDiffSum(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum sum of
// differences of subarrays by splitting
// array into non-overlapping subarrays
function maxDiffSum(arr, n)
{
// Stores the answer for prefix
// and initialize with zero
let dp = new Array(n).fill(0);
// Assume i-th index as right endpoint
for (let i = 0; i < n; i++) {
// Choose the current value as
// the maximum and minimum
let maxVal = arr[i], minVal = arr[i];
// Find the left endpoint and
// update the array dp[]
for (let j = i; j >= 0; j--) {
minVal = Math.min(minVal, arr[j]);
maxVal = Math.max(maxVal, arr[j]);
if (j - 1 >= 0)
dp[i] = Math.max(
dp[i], maxVal - minVal + dp[j - 1]);
else
dp[i] = Math.max(
dp[i], maxVal - minVal);
}
}
// Return answer
return dp[n - 1];
}
// Driver Code
let arr = [8, 1, 7, 9, 2];
let N = arr.length;
document.write(maxDiffSum(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
14
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por himanshu77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA