Suma de la diferencia absoluta de máximo y mínimo de todos los subarreglos

Dado un arreglo arr que contiene N enteros, la tarea es encontrar la suma de la diferencia absoluta de máximo y mínimo de todos los subarreglos.

Ejemplo:

Entrada: arr[] = {1, 4, 3}
Salida: 7
Explicación: Los siguientes son los seis subarreglos:
[1] : máximo – mínimo= 1 – 1 = 0
[4] : máximo – mínimo= 4 – 4 = 0
[3] : máximo – mínimo= 3 – 3 = 0
[1, 4] : máximo – mínimo= 4 – 1 = 3
[4, 3] : máximo – mínimo= 4 – 3 = 1
[1, 4, 3 ] : máximo – mínimo= 4 – 1 = 3
Como resultado, la suma total es: 0 + 0 + 0 + 3 + 1 + 3 = 7

Entrada: arr[] = {1, 6, 3}
Salida: 13

Enfoque: el enfoque es encontrar todos los subarreglos posibles y mantener su máximo y mínimo, luego usarlos para calcular la suma. Ahora, siga el siguiente paso para resolver este problema:

1. Cree una suma variable para almacenar la respuesta final e inicialícela en 0.
2. Ejecute un bucle de i=0 a i<N y en cada iteración:
   • Cree dos variables mx y mn para almacenar el máximo y el mínimo del subarreglo respectivamente.
   • Inicializa mx y mn a arr[i] .
   • Ahora, ejecute otro ciclo de j=i a j<N :
     • Cada iteración de este bucle se utiliza para calcular el máximo y el mínimo del subarreglo de i a j .
     • Entonces, cambie mx al máximo de mx y arr[j] .
     • Y cambie mn al mínimo de mn y arr[j] .
     • Ahora, suma (mx-mn) a la suma .
3. Devuelve sum como la respuesta final a este problema.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum
// of the absolute difference
// of maximum and minimum of all subarrays
int sumOfDiff(vector<int>& arr)
{
 
    int sum = 0;
    int n = arr.size();
 
    for (int i = 0; i < n; i++) {
        int mn = arr[i];
        int mx = arr[i];
 
        for (int j = i; j < n; j++) {
            mx = max(mx, arr[j]);
            mn = min(mn, arr[j]);
            sum += (mx - mn);
        }
    }
 
    return sum;
}
 
// Driver Code
int main()
{
 
    vector<int> arr = { 1, 6, 3 };
    cout << sumOfDiff(arr);
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
 
  // Function to find the sum
  // of the absolute difference
  // of maximum and minimum of all subarrays
  static int sumOfDiff(int []arr)
  {
 
    int sum = 0;
    int n = arr.length;
 
    for (int i = 0; i < n; i++) {
      int mn = arr[i];
      int mx = arr[i];
 
      for (int j = i; j < n; j++) {
        mx = Math.max(mx, arr[j]);
        mn = Math.min(mn, arr[j]);
        sum += (mx - mn);
      }
    }
 
    return sum;
  }
 
  // Driver Code
  public static void main(String args[])
  {
 
    int []arr = { 1, 6, 3 };
    System.out.println(sumOfDiff(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code for the above approach
 
# Function to find the sum
# of the absolute difference
# of maximum and minimum of all subarrays
def sumOfDiff(arr):
 
    sum = 0
    n = len(arr)
 
    for i in range(n):
        mn = arr[i]
        mx = arr[i]
 
        for j in range(i, n):
            mx = max(mx, arr[j])
            mn = min(mn, arr[j])
            sum += (mx - mn)
 
    return sum
 
# Driver Code
arr = [1, 6, 3]
print(sumOfDiff(arr))
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the sum of the absolute
// difference of maximum and minimum of all
// subarrays
static int sumOfDiff(int []arr)
{
    int sum = 0;
    int n = arr.Length;
     
    for(int i = 0; i < n; i++)
    {
        int mn = arr[i];
        int mx = arr[i];
         
        for(int j = i; j < n; j++)
        {
            mx = Math.Max(mx, arr[j]);
            mn = Math.Min(mn, arr[j]);
            sum += (mx - mn);
        }
    }
    return sum;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 1, 6, 3 };
     
    Console.Write(sumOfDiff(arr));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find the sum
      // of the absolute difference
      // of maximum and minimum of all subarrays
      function sumOfDiff(arr) {
 
          let sum = 0;
          let n = arr.length;
 
          for (let i = 0; i < n; i++) {
              let mn = arr[i];
              let mx = arr[i];
 
              for (let j = i; j < n; j++) {
                  mx = Math.max(mx, arr[j]);
                  mn = Math.min(mn, arr[j]);
                  sum += (mx - mn);
              }
          }
 
          return sum;
      }
 
      // Driver Code
      let arr = [1, 6, 3];
      document.write(sumOfDiff(arr));
 
// This code is contributed by Potta Lokesh
  </script>

13

Complejidad temporal: O(N ² )
Espacio auxiliar: O(1)