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