Suma del elemento mínimo de todos los subarreglos de un arreglo ordenado

Dada una array ordenada A de n enteros. La tarea es encontrar la suma del mínimo de todos los subarreglos posibles de A .

Ejemplos:  

Entrada: A = [1, 2, 4, 5] 
Salida: 23 
Las subsecuencias son [1], [2], [4], [5], [1, 2], [2, 4], [4, 5 ] [1, 2, 4], [2, 4, 5], [1, 2, 4, 5] 
Los mínimos son 1, 2, 4, 5, 1, 2, 4, 1, 2, 1. 
La suma es 23
Entrada: A = [1, 2, 3] 
Salida: 10 

Enfoque: el enfoque Naive es generar todos los subarreglos posibles, encontrar su mínimo y agregarlos al resultado. 
Enfoque Eficiente: Se da que la array está ordenada, así que observa que el elemento mínimo ocurre N veces, el segundo mínimo ocurre N-1 veces, y así sucesivamente… Tomemos un ejemplo:
 

arr[] = {1, 2, 3} 
Los subarreglos son {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3} 
Mínimo de cada subarreglo: { 1}, {2}, {3}, {1}, {2}, {1}. 
donde 
1 ocurre 3 veces, es decir, n veces cuando n = 3. 
2 ocurre 2 veces, es decir, n-1 veces cuando n = 3. 
3 ocurre 1 vez, es decir, n-2 veces cuando n = 3.

Entonces, recorra la array y agregue el elemento actual, es decir, (arr[i]* ni) a la suma.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum
// of minimum of all subarrays
int findMinSum(int arr[], int n)
{
 
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i] * (n - i);
 
    return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 5, 7, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findMinSum(arr, n);
 
    return 0;
}

// Java implementation of the above approach
class GfG
{
 
// Function to find the sum
// of minimum of all subarrays
static int findMinSum(int arr[], int n)
{
 
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i] * (n - i);
 
    return sum;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 5, 7, 8 };
    int n = arr.length;
 
    System.out.println(findMinSum(arr, n));
}
}
 
// This code is contributed by Prerna Saini

# Python3 implementation of the
# above approach
 
# Function to find the sum
# of minimum of all subarrays
def findMinSum(arr, n):
    sum = 0
    for i in range(0, n):
        sum += arr[i] * (n - i)
    return sum
 
# Driver code
arr = [3, 5, 7, 8 ]
n = len(arr)
 
print(findMinSum(arr, n))
 
# This code has been contributed
# by 29AjayKumar

// C# implementation of the above approach
using System;
 
class GfG
{
 
// Function to find the sum
// of minimum of all subarrays
static int findMinSum(int []arr, int n)
{
 
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i] * (n - i);
 
    return sum;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 3, 5, 7, 8 };
    int n = arr.Length;
 
    Console.WriteLine(findMinSum(arr, n));
}
}
 
// This code is contributed by Arnab Kundu

<?php
 
// PHP implementation of the above approach
// Function to find the sum
// of minimum of all subarrays
function findMinSum($arr,$n)
{
 
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $arr[$i] * ($n - $i);
 
    return $sum;
}
 
// Driver code
$arr = array( 3, 5, 7, 8 );
$n = count($arr);
 
echo findMinSum($arr, $n);
     
// This code is contributed by Arnab Kundu
?>

<script>
 
// Javascript implementation of the above approach
 
// Function to find the sum
// of minimum of all subarrays
function findMinSum(arr, n)
{
 
    var sum = 0;
    for (var i = 0; i < n; i++)
        sum += arr[i] * (n - i);
 
    return sum;
}
 
// Driver code
var arr = [ 3, 5, 7, 8 ];
var n = arr.length;
document.write( findMinSum(arr, n));
 
</script>

49

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Nota: Para encontrar la Suma del elemento máximo de todos los subarreglos en una array ordenada , simplemente recorra la array en orden inverso y aplique la misma fórmula para la Suma.