Diferencia máxima de suma de prefijos para todos los índices de dos arrays dadas

Dados 2 arreglos de enteros a[] y s[] ambos de tamaño N . La tarea es encontrar la diferencia máxima de la suma de prefijos para todos los índices de las arrays dadas.

Ejemplos:

Entrada: N = 5, a[] = {20, 20, 35, 20, 35}, s[] = {21, 31, 34, 41, 14}
Salida: 32
Explicación: Después de la suma del prefijo, las arrays son a[ ] = {20, 40, 75, 95, 130} 
y b[] = {21, 52, 86, 127, 141} para S. La diferencia máxima es (127 – 95) = 32 para la 4ª posición.

Entrada: N = 1, a[] = {32}, s[] = {15}
Salida: A, 17
Explicación: La diferencia más alta (ya que solo un elemento) es 32 – 15 = 17.

Enfoque: este problema se puede resolver calculando la suma del prefijo en ambas arrays y luego comparando las diferencias para cada índice. Siga los pasos a continuación para resolver el problema:

• Itere sobre el rango [0, n) usando la variable i y calcule la suma del prefijo para ambas arrays.
• Calcule la diferencia de la suma de prefijos para cada índice.
• Devolver la máxima diferencia.

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 get the winner
int getWinner(int a[], int s[], int N)
{
    int maxDiff = abs(a[0] - s[0]);
 
    // Calculating prefix sum
    for (int i = 1; i < N; i++) {
        a[i] += a[i - 1];
        s[i] += s[i - 1];
        maxDiff = max(maxDiff,
                      abs(a[i] - s[i]));
    }
 
    // Return the result
    return maxDiff;
}
 
// Driver Code
int main()
{
    int N = 5;
 
    int a[] = { 20, 20, 35, 20, 35 },
        s[] = { 21, 31, 34, 41, 14 };
 
    cout << getWinner(a, s, N);
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to get the winner
static int getWinner(int a[], int s[], int N)
{
    int maxDiff = Math.abs(a[0] - s[0]);
 
    // Calculating prefix sum
    for (int i = 1; i < N; i++) {
        a[i] += a[i - 1];
        s[i] += s[i - 1];
        maxDiff = Math.max(maxDiff,
                      Math.abs(a[i] - s[i]));
    }
 
    // Return the result
    return maxDiff;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
 
    int a[] = { 20, 20, 35, 20, 35 },
        s[] = { 21, 31, 34, 41, 14 };
 
    System.out.print(getWinner(a, s, N));
}
}
 
// This code is contributed by Rajput-Ji

# python3 program for the above approach
 
# Function to get the winner
 
 
def getWinner(a, s, N):
 
    maxDiff = abs(a[0] - s[0])
 
    # Calculating prefix sum
    for i in range(1, N):
        a[i] += a[i - 1]
        s[i] += s[i - 1]
        maxDiff = max(maxDiff, abs(a[i] - s[i]))
 
    # Return the result
    return maxDiff
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
 
    a = [20, 20, 35, 20, 35]
    s = [21, 31, 34, 41, 14]
 
    print(getWinner(a, s, N))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG {
 
  // Function to get the winner
  static int getWinner(int[] a, int[] s, int N)
  {
    int maxDiff = Math.Abs(a[0] - s[0]);
 
    // Calculating prefix sum
    for (int i = 1; i < N; i++) {
      a[i] += a[i - 1];
      s[i] += s[i - 1];
      maxDiff
        = Math.Max(maxDiff, Math.Abs(a[i] - s[i]));
    }
 
    // Return the result
    return maxDiff;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 5;
 
    int[] a = { 20, 20, 35, 20, 35 };
    int[] s = { 21, 31, 34, 41, 14 };
 
    Console.WriteLine(getWinner(a, s, N));
  }
}
 
// This code is contributed by ukasp.

<script>
      // JavaScript code for the above approach
      // Function to get the winner
      function getWinner(a, s, N) {
          let maxDiff = Math.abs(a[0] - s[0]);
 
          // Calculating prefix sum
          for (let i = 1; i < N; i++) {
              a[i] += a[i - 1];
              s[i] += s[i - 1];
              maxDiff = Math.max(maxDiff,
                  Math.abs(a[i] - s[i]));
          }
 
          // Return the result
          return maxDiff;
      }
 
      // Driver Code
 
      let N = 5;
 
      let a = [20, 20, 35, 20, 35],
          s = [21, 31, 34, 41, 14];
 
      document.write(getWinner(a, s, N));
 
// This code is contributed by Potta Lokesh
  </script>

32

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