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