Subarreglo alterno de suma máxima

Dado un arreglo arr[] de tamaño N, la tarea es encontrar la suma alterna máxima de un subarreglo posible para un arreglo dado.

 Suma de subarreglo alternante: considerando un subarreglo {arr[i], arr[j]}, la suma alterna del subarreglo es arr[i] – arr[i + 1] + arr[i + 2] – …….. (+ / -) arr[j].

Ejemplos:

Entrada: arr[] = {-4, -10, 3, 5}
Salida: 9
Explicación: Subarreglo {arr[0], arr[2]} = {-4, -10, 3}. Por lo tanto, la suma de este subarreglo es 9.

Entrada: arr[] = {-1, 2, -1, 4, 7}
Salida: 7

Enfoque : El problema dado se puede resolver usando Programación Dinámica . Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos sum como 0 , que contendrá una suma de subarreglo alternante máxima y una variable, digamos sumSoFar , para almacenar la suma de los subarreglos a partir de índices pares en el primer ciclo y la suma a partir de índices impares, en el 2 segundo bucle.
  • En cada iteración de ambos bucles, actualice sum como max(sum, sumSoFar) .
  • Finalmente, devuelve la suma alterna máxima almacenada en la variable sum .

 A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum alternating
// sum of a subarray for the given array
int alternatingSum(int arr[],int n)
{
  int sum = 0;
  int sumSoFar = 0;
 
  // Traverse the array
  for (int i = 0; i < n; i++) {
 
    // Store sum of subarrays
    // starting at even indices
    if (i % 2 == 1) {
 
      sumSoFar -= arr[i];
    }
    else {
 
      sumSoFar = max(
        sumSoFar + arr[i], arr[i]);
    }
 
    // Update sum
    sum = max(sum, sumSoFar);
  }
 
  sumSoFar = 0;
 
  // Traverse the array
  for (int i = 1; i < n; i++) {
 
    // Store sum of subarrays
    // starting at odd indices
    if (i % 2 == 0) {
      sumSoFar -= arr[i];
    }
    else {
      sumSoFar = max(
        sumSoFar + arr[i], arr[i]);
    }
 
    // Update sum
    sum = max(sum, sumSoFar);
  }
  return sum;
}
 
// Driver code
int main()
{
 
  // Given Input
  int arr[] ={ -4, -10, 3, 5 };
  int n = sizeof(arr)/sizeof(arr[0]);
   
  // Function call
  int ans = alternatingSum(arr,n);
 
  cout<<ans<<endl;
  return 0;
}
 
// This code is contributed by Potta Lokesh

Java

// Java implementation for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the maximum alternating
    // sum of a subarray for the given array
    public static int alternatingSum(int[] arr)
    {
        int sum = 0;
        int sumSoFar = 0;
 
        // Traverse the array
        for (int i = 0; i < arr.length; i++) {
 
            // Store sum of subarrays
            // starting at even indices
            if (i % 2 == 1) {
 
                sumSoFar -= arr[i];
            }
            else {
 
                sumSoFar = Math.max(
                    sumSoFar + arr[i], arr[i]);
            }
 
            // Update sum
            sum = Math.max(sum, sumSoFar);
        }
 
        sumSoFar = 0;
 
        // Traverse the array
        for (int i = 1; i < arr.length; i++) {
 
            // Store sum of subarrays
            // starting at odd indices
            if (i % 2 == 0) {
                sumSoFar -= arr[i];
            }
            else {
                sumSoFar = Math.max(
                    sumSoFar + arr[i], arr[i]);
            }
 
            // Update sum
            sum = Math.max(sum, sumSoFar);
        }
        return sum;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Given Input
        int arr[] = new int[] { -4, -10, 3, 5 };
 
        // Function call
        int ans = alternatingSum(arr);
 
        System.out.println(ans);
    }
}

Python3

# Python implementation for the above approach
 
# Function to find the maximum alternating
# sum of a subarray for the given array
def alternatingSum(arr, n):
    sum_ = 0
    sumSoFar = 0
     
    # Traverse the array
    for i in range(n):
       
      # Store sum of subarrays
       # starting at even indices
        if i % 2 == 1:
            sumSoFar -= arr[i]
        else:
            sumSoFar = max(arr[i], sumSoFar + arr[i])
             
            # Update sum
        sum_ = max(sum_, sumSoFar)
 
    sumSoFar = 0
     
    # Traverse array
    for i in range(1, n):
       
      # Store sum of subarrays
      # starting at odd indices
        if i % 2 == 0:
            sumSoFar -= arr[i]
        else:
            sumSoFar = max(arr[i], sumSoFar + arr[i])
        sum_ = max(sum_, sumSoFar)
         
        # update sum
    return sum_
 
# given array
arr = [-4, -10, 3, 5]
n = len(arr)
 
# return sum
ans = alternatingSum(arr, n)
print(ans)
 
# This code is contributed by Parth Manchanda

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the maximum alternating
// sum of a subarray for the given array
static int alternatingSum(int []arr,int n)
{
    int sum = 0;
    int sumSoFar = 0;
     
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
     
        // Store sum of subarrays
        // starting at even indices
        if (i % 2 == 1)
        {
            sumSoFar -= arr[i];
        }
        else
        {
            sumSoFar = Math.Max(
            sumSoFar + arr[i], arr[i]);
        }
         
        // Update sum
        sum = Math.Max(sum, sumSoFar);
    }
     
    sumSoFar = 0;
     
    // Traverse the array
    for(int i = 1; i < n; i++)
    {
     
        // Store sum of subarrays
        // starting at odd indices
        if (i % 2 == 0)
        {
            sumSoFar -= arr[i];
        }
        else
        {
            sumSoFar = Math.Max(
            sumSoFar + arr[i], arr[i]);
        }
         
        // Update sum
        sum = Math.Max(sum, sumSoFar);
    }
    return sum;
}
 
// Driver code
public static void Main()
{
     
    // Given Input
    int []arr = { -4, -10, 3, 5 };
    int n = arr.Length;
     
    // Function call
    int ans = alternatingSum(arr,n);
     
    Console.Write(ans);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
// JavaScript implementation for the above approach
    // Function to find the maximum alternating
    // sum of a subarray for the given array
    function alternatingSum(arr)
    {
        var sum = 0;
        var sumSoFar = 0;
 
        // Traverse the array
        for (var i = 0; i < arr.length; i++) {
 
            // Store sum of subarrays
            // starting at even indices
            if (i % 2 == 1) {
 
                sumSoFar -= arr[i];
            }
            else {
 
                sumSoFar = Math.max(
                    sumSoFar + arr[i], arr[i]);
            }
 
            // Update sum
            sum = Math.max(sum, sumSoFar);
        }
 
        sumSoFar = 0;
 
        // Traverse the array
        for (var i = 1; i < arr.length; i++) {
 
            // Store sum of subarrays
            // starting at odd indices
            if (i % 2 == 0) {
                sumSoFar -= arr[i];
            }
            else {
                sumSoFar = Math.max(
                    sumSoFar + arr[i], arr[i]);
            }
 
            // Update sum
            sum = Math.max(sum, sumSoFar);
        }
        return sum;
    }
 
    // Driver code
        // Given Input
        var arr = new Array ( -4, -10, 3, 5 );
 
        // Function call
        var ans = alternatingSum(arr);
        document.write(ans);
         
    // This code is contributed by  shivanisinghss2110
</script>
Producción: 

9

 

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

Publicación traducida automáticamente

Artículo escrito por abhinaygupta98 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 *