Array de suma de sufijos – Barcelona Geeks

Array de suma de sufijos Dada una array arr[] de tamaño N , la tarea es calcular y devolver su array de suma de sufijos .

Suffix Sum es una técnica de cálculo previo en la que se calcula la suma de todos los elementos de la array original desde un índice i hasta el final de la array.

Por lo tanto, esta array de suma de sufijos se creará utilizando la relación:

$suffixSum[i] = arr[i] + arr[i+1] + arr[i+2] … +arr[n-1]$

Ejemplos:

Entrada : arr[] = { 15, 10, 25, 5, 10, 20 } , N = 6
Salida : suffixSum[] = { 85, 70, 60, 35, 30, 20}
Explicación : mientras recorre la array desde atrás , siga agregando el elemento desde atrás con el elemento en el índice actual.
suffixSum[5] = 20,
suffixSum[4] =suffixSum[5] + arr[4] = 20+10 = 30 ,
suffixSum[3] = suffixSum[4] + arr[3] = 30+5 = 35 y así en.

Entrada : arr[] = {10, 14, 16, 20}, n = 6
Salida : suffixSum[] = {60, 50, 36, 20}
Explicación : suffixSum[3] = 20,
suffixSum[2] =suffixSum[ 3] + arr[2] = 20+16 = 36 ,
suffixSum[1] = suffixSum[2] + arr[1] = 36+14 = 40 y así sucesivamente.

Enfoque : para llenar la array de suma de sufijos, ejecutamos el índice N-1 a 0 y seguimos agregando el elemento actual con el valor anterior en la array de suma de sufijos.

Cree una array de tamaño N para almacenar la suma del sufijo.
Inicialice el último elemento de la array de suma de sufijos con el último elemento de la array original
suffixSum[n-1] = arr[n-1]
Atraviesa la array original de N-2 a 0
- Para cada índice encuentro el sufijo sum y lo almaceno en suffixSum[i]
- sumasufijo[i] = sumasufijo[i + 1] + arr[i]
Devuelve la array de suma de sufijos calculada.

A continuación se muestra la implementación del enfoque anterior para crear una array de suma de sufijos:

C++

// C++ program for Implementing
// suffix sum array
#include <bits/stdc++.h>
using namespace std;
 
// Function to create suffix sum array
vector<int> createSuffixSum(vector<int> arr, int n)
{
    // Create an array to store the suffix sum
    vector<int> suffixSum(n, 0);
 
    // Initialize the last element of
    // suffix sum array with last element
    // of original array
    suffixSum[n - 1] = arr[n - 1];
 
    // Traverse the array from n-2 to 0
    for (int i = n - 2; i >= 0; i--)
 
        // Adding current element
        // with previous element from back
        suffixSum[i] = suffixSum[i + 1] + arr[i];
 
    // Return the computed suffixSum array
    return suffixSum;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 10, 14, 16, 20 };
    int N = arr.size();
 
    // Function call to fill suffix sum array
    vector<int> suffixSum = createSuffixSum(arr, N);
 
    // Printing the computed suffix sum array
    cout << "Suffix sum array: ";
    for (int i = 0; i < N; i++)
        cout << suffixSum[i] << " ";
}

Java

// Java program for Implementing
// suffix sum array
import java.util.*;
public class GFG {
 
  // Function to create suffix sum array
  static int[] createSuffixSum(int[] arr, int n)
  {
 
    // Create an array to store the suffix sum
    int[] suffixSum = new int[n];
 
    for (int i = 0; i < n; i++) {
      suffixSum[i] = 0;
    }
 
    // Initialize the last element of
    // suffix sum array with last element
    // of original array
    suffixSum[n - 1] = arr[n - 1];
 
    // Traverse the array from n-2 to 0
    for (int i = n - 2; i >= 0; i--)
 
      // Adding current element
      // with previous element from back
      suffixSum[i] = suffixSum[i + 1] + arr[i];
 
    // Return the computed suffixSum array
    return suffixSum;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int[] arr = { 10, 14, 16, 20 };
    int N = arr.length;
 
    // Function call to fill suffix sum array
    int[] suffixSum = createSuffixSum(arr, N);
 
    // Printing the computed suffix sum array
    System.out.print("Suffix sum array: ");
    for (int i = 0; i < N; i++)
      System.out.print(suffixSum[i] + " ");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# python3 program for Implementing
# suffix sum array
 
# Function to create suffix sum array
def createSuffixSum(arr, n):
 
    # Create an array to store the suffix sum
    suffixSum = [0 for _ in range(n)]
 
    # Initialize the last element of
    # suffix sum array with last element
    # of original array
    suffixSum[n - 1] = arr[n - 1]
 
    # Traverse the array from n-2 to 0
    for i in range(n-2, -1, -1):
 
        # Adding current element
        # with previous element from back
        suffixSum[i] = suffixSum[i + 1] + arr[i]
 
    # Return the computed suffixSum array
    return suffixSum
 
# Driver Code
if __name__ == "__main__":
 
    arr = [10, 14, 16, 20]
    N = len(arr)
 
    # Function call to fill suffix sum array
    suffixSum = createSuffixSum(arr, N)
 
    # Printing the computed suffix sum array
    print("Suffix sum array: ", end="")
    for i in range(0, N):
        print(suffixSum[i], end=" ")
 
    # This code is contributed by rakeshsahni

C#

// C# program for Implementing
// suffix sum array
using System;
class GFG {
 
  // Function to create suffix sum array
  static int[] createSuffixSum(int[] arr, int n)
  {
 
    // Create an array to store the suffix sum
    int[] suffixSum = new int[n];
 
    for (int i = 0; i < n; i++) {
      suffixSum[i] = 0;
    }
 
    // Initialize the last element of
    // suffix sum array with last element
    // of original array
    suffixSum[n - 1] = arr[n - 1];
 
    // Traverse the array from n-2 to 0
    for (int i = n - 2; i >= 0; i--)
 
      // Adding current element
      // with previous element from back
      suffixSum[i] = suffixSum[i + 1] + arr[i];
 
    // Return the computed suffixSum array
    return suffixSum;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 10, 14, 16, 20 };
    int N = arr.Length;
 
    // Function call to fill suffix sum array
    int[] suffixSum = createSuffixSum(arr, N);
 
    // Printing the computed suffix sum array
    Console.Write("Suffix sum array: ");
    for (int i = 0; i < N; i++)
      Console.Write(suffixSum[i] + " ");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
      // JavaScript code for the above approach
 
      // Function to create suffix sum array
      function createSuffixSum(arr, n)
      {
       
          // Create an array to store the suffix sum
          let suffixSum = new Array(n).fill(0);
 
          // Initialize the last element of
          // suffix sum array with last element
          // of original array
          suffixSum[n - 1] = arr[n - 1];
 
          // Traverse the array from n-2 to 0
          for (let i = n - 2; i >= 0; i--)
 
              // Adding current element
              // with previous element from back
              suffixSum[i] = suffixSum[i + 1] + arr[i];
 
          // Return the computed suffixSum array
          return suffixSum;
      }
 
      // Driver Code
      let arr = [10, 14, 16, 20];
      let N = arr.length;
 
      // Function call to fill suffix sum array
      let suffixSum = createSuffixSum(arr, N);
 
      // Printing the computed suffix sum array
      document.write("Suffix sum array: ")
      for (let i = 0; i < N; i++)
          document.write(suffixSum[i] + " ");
 
     // This code is contributed by Potta Lokesh
  </script>

Producción

Suffix sum array: 60 50 36 20

Complejidad de tiempo : O (N), para atravesar la array original para calcular la suma de sufijos.
Espacio auxiliar : O (N), para almacenar la array de suma de sufijos.

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta