Suma de todos los subarreglos | Serie 1

Dada una array de enteros ‘arr[]’ de tamaño n, encuentre la suma de todas las sub-arrays de la array dada. 

Ejemplos: 

Input   : arr[] = {1, 2, 3}
Output  : 20
Explanation : {1} + {2} + {3} + {2 + 3} + 
              {1 + 2} + {1 + 2 + 3} = 20

Input  : arr[] = {1, 2, 3, 4}
Output : 50

Método 1 (Solución simple) 
Una solución simple es generar todos los subconjuntos y calcular su suma.

A continuación se muestra la implementación de la idea anterior.  

C++

// Simple C++ program to compute sum of
// subarray elements
#include<bits/stdc++.h>
using namespace std;
 
// Computes sum all sub-array
long int SubArraySum(int arr[], int n)
{
    long int result = 0,temp=0;
 
    // Pick starting point
    for (int i=0; i <n; i++)
    {
        // Pick ending point
        temp=0;
        for (int j=i; j<n; j++)
        {
            // sum subarray between current
            // starting and ending points
            temp+=arr[j];
            result += temp ;
        }
    }
    return result ;
}
 
// driver program to test above function
int main()
{
    int arr[] = {1, 2, 3} ;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum of SubArray : "
          << SubArraySum(arr, n) << endl;
    return 0;
}

Java

// Simple Java program to compute sum of
// subarray elements
class GFG {
     
    // Computes sum all sub-array
    public static long SubArraySum(int arr[], int n)
    {
        long result = 0,temp=0;
      
        // Pick starting point
        for (int i = 0; i < n; i ++)
        {
            // Pick ending point
            temp=0;
            for (int j = i; j < n; j ++)
            {
                // sum subarray between current
                // starting and ending points
                temp+=arr[j];
                result += temp ;
            }
        }
        return result ;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3} ;
        int n = arr.length;
        System.out.println("Sum of SubArray : " +
                          SubArraySum(arr, n));
    }
}
// This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 program to compute
# sum of subarray elements
 
# Computes sum all sub-array
def SubArraySum(arr, n):
    temp,result = 0,0
 
    # Pick starting point
    for i in range(0, n):
 
        # Pick ending point
        temp=0;
        for j in range(i, n):
 
            # sum subarray between
            # current starting and
            # ending points
            temp+=arr[j]
            result += temp
    return result
 
# driver program
arr = [1, 2, 3]
n = len(arr)
print ("Sum of SubArray :"
       ,SubArraySum(arr, n))
 
# This code is contributed by
# TheGameOf256.

C#

// Simple C# program to compute sum of
// subarray elements
using System;
 
class GFG {
     
    // Computes sum all sub-array
    public static long SubArraySum(int []arr,
                                      int n)
    {
        long result = 0,temp=0;
     
        // Pick starting point
        for (int i = 0; i < n; i ++)
        {
            // Pick ending point
            temp=0;
            for (int j = i; j < n; j ++)
            {
                 
                // sum subarray between current
                // starting and ending points
                temp+=arr[j];
                result += temp ;
            }
        }
        return result ;
    }
     
    // Driver Code
    public static void Main()
    {
        int []arr = {1, 2, 3} ;
        int n = arr.Length;
        Console.Write("Sum of SubArray : " +
                        SubArraySum(arr, n));
    }
}
 
// This code is contributed by nitin mittal

PHP

<?php
// Simple PHP program to
// compute sum of subarray
// elements Computes sum
// all sub-array
 
function SubArraySum($arr, $n)
{
    $result = 0;
    $temp=0;
    // Pick starting point
    for ($i = 0; $i < $n; $i++)
    {
        // Pick ending point
        $temp=0;
        for ($j = $i; $j < $n; $j++)
        {
            // sum subarray between
            // current starting and
            // ending points
            $temp+=$arr[$j]
            $result += $temp ;
        }
    }
    return $result ;
}
 
// Driver Code
$arr = array(1, 2, 3) ;
$n = sizeof($arr);
echo "Sum of SubArray : ",
    SubArraySum($arr, $n),"\n";
     
// This code is contributed by ajit
?>

Javascript

<script>
 
// Simple Javascript program to compute sum of
// subarray elements
 
// Computes sum all sub-array
function SubArraySum(arr, n)
{
    let result = 0,temp=0;
 
    // Pick starting point
    for (let i=0; i <n; i++)
    {
        // Pick ending point
        temp=0;
        for (let j=i; j<n; j++)
        {
            // sum subarray between current
            // starting and ending points
            temp+=arr[j];
            result += temp ;
        }
    }
    return result ;
}
 
// driver program to test above function
  
    let arr = [1, 2, 3] ;
    let n = arr.length;
    document.write("Sum of SubArray : "
    + SubArraySum(arr, n) + "<br>");
     
// This code is contributed by Mayank Tyagi
 
</script>

Producción: 

Sum of SubArray : 20

Complejidad del tiempo : O(n 2

Método 2 (usando prefijo-suma)

Podemos construir una array de suma de prefijos y extraer la suma de subarreglo entre los índices inicial y final.
A continuación se muestra la implementación de la idea anterior.  

Java

// Simple Java program to compute sum of
// subarray elements
class GFG {
    
  //Construct prefix-sum array
      public static void buildPrefixSumArray(int arr[], int n, int prefixSumArray[])
      {
        prefixSumArray[0] = arr[0];
        // Adding present element with previous element
        for (int i = 1; i < n; i++)
            prefixSumArray[i] = prefixSumArray[i - 1] + arr[i];
      }
  // Computes sum all sub-array
     public static long SubArraySum(int arr[], int n)
     {
         long result = 0,sum=0;
        int[] prefixSumArr= new int[n];
 
        buildPrefixSumArray(arr,  n,  prefixSumArr);
         // Pick starting point
         for (int i = 0; i < n; i ++)
         {
             // Pick ending point
             sum=0;
             for (int j = i; j < n; j ++)
             {
                 // sum subarray between current
                 // starting and ending points
                if(i!=0)
                 {
                  sum= prefixSumArr[j] - prefixSumArr[i-1];
 
                 }
               else
                    sum=prefixSumArr[j];
            result += sum;
             }
         }
         return result ;
     }
 
   /* Driver program to test above function */
   public static void main(String[] args)
   {
       int arr[] = {1, 2, 3, 4} ;
       int n = arr.length;
       System.out.println("Sum of SubArray : " +
                         SubArraySum(arr, n));
   }
}
Producción

Sum of SubArray : 50

Complejidad del tiempo : O(n 2

Método 3 (solución eficiente) 
Si observamos de cerca, observamos un patrón. Tomemos un ejemplo  

arr[] = [1, 2, 3], n = 3
All subarrays :  [1], [1, 2], [1, 2, 3], 
                 [2], [2, 3], [3]
here first element 'arr[0]' appears 3 times    
     second element 'arr[1]' appears 4 times  
     third element 'arr[2]' appears 3 times

Every element arr[i] appears in two types of subsets:
i)  In subarrays beginning with arr[i]. There are 
    (n-i) such subsets. For example [2] appears
    in [2] and [2, 3].
ii) In (n-i)*i subarrays where this element is not
    first element. For example [2] appears in 
    [1, 2] and [1, 2, 3].

Total of above (i) and (ii) = (n-i) + (n-i)*i 
                            = (n-i)(i+1)
                                  
For arr[] = {1, 2, 3}, sum of subarrays is:
  arr[0] * ( 0 + 1 ) * ( 3 - 0 ) + 
  arr[1] * ( 1 + 1 ) * ( 3 - 1 ) +
  arr[2] * ( 2 + 1 ) * ( 3 - 2 ) 

= 1*3 + 2*4 + 3*3 
= 20

A continuación se muestra la implementación de la idea anterior. 

C++

// Efficient C++ program to compute sum of
// subarray elements
#include<bits/stdc++.h>
using namespace std;
 
//function compute sum all sub-array
long int SubArraySum( int arr[] , int n )
{
    long int result = 0;
 
    // computing sum of subarray using formula
    for (int i=0; i<n; i++)
        result += (arr[i] * (i+1) * (n-i));
 
    // return all subarray sum
    return result ;
}
 
// driver program to test above function
int main()
{
    int arr[] = {1, 2, 3} ;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum of SubArray : "
         << SubArraySum(arr, n) << endl;
    return 0;
}

Java

// Efficient Java program to compute sum of
// subarray elements
class GFG {
     
    //function compute sum all sub-array
    public static long SubArraySum( int arr[] , int n )
    {
        long result = 0;
      
        // computing sum of subarray using formula
        for (int i=0; i<n; i++)
            result += (arr[i] * (i+1) * (n-i));
      
        // return all subarray sum
        return result ;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3} ;
        int n = arr.length;
        System.out.println("Sum of SubArray " +
                           SubArraySum(arr, n));
    }
}
// This code is contributed by Arnav Kr. Mandal.

Python3

#Python3 code to compute
# sum of subarray elements
 
#function compute sum
# all sub-array
def SubArraySum(arr, n ):
    result = 0
 
    # computing sum of subarray
    # using formula
    for i in range(0, n):
        result += (arr[i] * (i+1) * (n-i))
 
    # return all subarray sum
    return result
 
# driver program
arr = [1, 2, 3]
n = len(arr)
print ("Sum of SubArray : ",
      SubArraySum(arr, n))
 
# This code is contributed by
# TheGameOf256.

C#

// Efficient C# program
// to compute sum of
// subarray elements
using System;
 
class GFG
{
         
    // function compute
    // sum all sub-array
    public static long SubArraySum(int []arr ,
                                   int n )
    {
        long result = 0;
     
        // computing sum of
        // subarray using formula
        for (int i = 0; i < n; i++)
            result += (arr[i] *
                      (i + 1) * (n - i));
     
        // return all subarray sum
        return result ;
    }
     
    // Driver code
    static public void Main ()
    {
        int []arr = {1, 2, 3} ;
        int n = arr.Length;
        Console.WriteLine("Sum of SubArray: " +
                          SubArraySum(arr, n));
    }
}
 
// This code is contributed by akt_mit

PHP

<?php
// Efficient PHP program to compute
// sum of subarray elements
 
//function compute sum all sub-array
function SubArraySum($arr , $n)
{
    $result = 0;
 
    // computing sum of subarray
    // using formula
    for ($i = 0; $i < $n; $i++)
        $result += ($arr[$i] *
                    ($i + 1) *
                    ($n - $i));
 
    // return all subarray sum
    return $result ;
}
 
// Driver Code
$arr = array(1, 2, 3) ;
$n = sizeof($arr);
echo "Sum of SubArray : ",
      SubArraySum($arr, $n) ,"\n";
 
 
#This code is contributed by aj_36
?>

Javascript

<script>
 
// Efficient Javascript program
// to compute sum of subarray elements
 
// Function compute
// sum all sub-array
function SubArraySum(arr, n)
{
    let result = 0;
  
    // Computing sum of
    // subarray using formula
    for(let i = 0; i < n; i++)
        result += (arr[i] * (i + 1) *
                            (n - i));
  
    // Return all subarray sum
    return result ;
}
 
// Driver code
let arr = [ 1, 2, 3 ];
let n = arr.length;
 
document.write("Sum of SubArray : " +
               SubArraySum(arr, n));
                
// This code is contributed by divyesh072019
 
</script>

Producción : 

Sum of SubArray : 20

Complejidad de tiempo: O(n)
Referencia: 
https://www.quora.com/Can-we-find-the-sum-of-all-sub-arrays-of-an-integer-array-in-On-time
Suma de todas las subsecuencias de una array
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *