Dada una lista de longitud N con enteros positivos y negativos. La tarea es elegir la subsecuencia alterna más larga de la secuencia dada (es decir, el signo de cada elemento siguiente es el opuesto al signo del elemento actual). Entre todas esas subsecuencias, tenemos que elegir una que tenga la suma máxima de elementos y mostrar esa suma.
Ejemplos:
Entrada: lista = [-2 10 3 -8 -4 -1 5 -2 -3 1]
Salida: 11
Explicación:
La subsecuencia más grande con la suma más grande es [-2 10 -1 5 -2 1] con longitud 6.Entrada: list=[12 4 -5 7 -9]
Salida: 5
Explicación:
La subsecuencia más grande con la suma más grande es [12 -5 7 -9] con longitud 4.
Enfoque: La solución se puede alcanzar mediante el siguiente enfoque:-
- Para obtener una subsecuencia alterna con la longitud máxima y la suma más grande, recorreremos la lista completa (longitud de la lista) -1 veces para comparar signos de elementos consecutivos.
- Durante el recorrido, si obtenemos más de 1 elemento consecutivo del mismo signo (exp. 1 2 4), agregaremos el elemento máximo de ellos a otra lista llamada large . entonces de 1 2 y 4 agregaremos 4 a otra lista.
- Si tenemos elementos consecutivos de signo opuesto, simplemente agregaremos esos elementos a esa lista llamada large .
- Finalmente, la lista llamada grande tendrá la subsecuencia alterna más larga con los elementos más grandes.
- Ahora, tendremos que calcular la suma de todos los elementos de esa lista llamada large .
Tomemos un ejemplo, tenemos una lista [1, 2, 3, -2, -5, 1, -7, -1].
- Al recorrer esta lista de longitud 1 veces, obtenemos 1, 2, 3 con el mismo signo, por lo que agregaremos el mayor de estos (es decir, 3) a otra lista llamada grande aquí.
Por lo tanto grande = [3]- Ahora -2 y -5 tienen el mismo signo, por lo que añadiremos -2 a otra Lista.
grande=[3, -2]- Ahora, los signos de 1 y -7 son opuestos, por lo que agregaremos 1 a grande.
grande=[3, -2, 1]- Para -7, -1 los signos son los mismos, por lo tanto agregue -1 a grande.
grande=[3, -2, 1, -1]- Calcular la suma = 3 – 2 + 1 – 1 = 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// longest alternating subsequence
// which has the maximum sum
#include<bits/stdc++.h>
using namespace std;
int calculateMaxSum(int n, int li[])
{
// Creating a temporary list ar to
// every time store same sign element
// to calculate maximum element from
// that list ar
vector<int> ar;
// Appending 1st element of list li
// to the ar
ar.push_back(li[0]);
// Creating list to store maximum
// values
vector<int> large;
for(int j = 0; j < n - 1; j++)
{
// If both number are positive
// then append (j + 1)th element
// to temporary list ar
if(li[j] > 0 and li[j + 1] > 0)
{
ar.push_back(li[j + 1]);
}
else if(li[j] > 0 and li[j + 1] < 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.push_back(*max_element(ar.begin(),
ar.end()));
// Empty ar list to re-append
// next elements
ar.clear();
ar.push_back(li[j + 1]);
}
else if(li[j] < 0 and li[j + 1] > 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.push_back(*max_element(ar.begin(),
ar.end()));
// Empty ar list to re-append
// next elements
ar.clear();
ar.push_back(li[j + 1]);
}
else
{
// If both number are negative
// then append (j + 1)th element
// to temporary list ar
ar.push_back(li[j + 1]);
}
}
// The final Maximum element in ar list
// also needs to be appended to large list
large.push_back(*max_element(ar.begin(),
ar.end()));
// Returning the sum of all elements
// from largest elements list with
// largest alternating subsequence size
int sum = 0;
for(int i = 0; i < large.size(); i++)
sum += large[i];
return sum;
}
// Driver code
int main()
{
int list[] = { -2, 8, 3, 8, -4, -15,
5, -2, -3, 1 };
int N = sizeof(list) / sizeof(list[0]);
cout << (calculateMaxSum(N, list));
}
// This code is contributed by Bhupendra_Singh
Java
// Java implementation to find the
// longest alternating subsequence
// which has the maximum sum
import java.util.*;
class GFG{
static int calculateMaxSum(int n, int li[])
{
// Creating a temporary list ar to
// every time store same sign element
// to calculate maximum element from
// that list ar
Vector<Integer> ar = new Vector<>();
// Appending 1st element of list li
// to the ar
ar.add(li[0]);
// Creating list to store maximum
// values
Vector<Integer> large = new Vector<>();
for(int j = 0; j < n - 1; j++)
{
// If both number are positive
// then append (j + 1)th element
// to temporary list ar
if(li[j] > 0 && li[j + 1] > 0)
{
ar.add(li[j + 1]);
}
else if(li[j] > 0 && li[j + 1] < 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.add(Collections.max(ar));
// Empty ar list to re-append
// next elements
ar.clear();
ar.add(li[j + 1]);
}
else if(li[j] < 0 && li[j + 1] > 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.add(Collections.max(ar));
// Empty ar list to re-append
// next elements
ar.clear();
ar.add(li[j + 1]);
}
else
{
// If both number are negative
// then append (j + 1)th element
// to temporary list ar
ar.add(li[j + 1]);
}
}
// The final Maximum element in ar list
// also needs to be appended to large list
large.add(Collections.max(ar));
// Returning the sum of all elements
// from largest elements list with
// largest alternating subsequence size
int sum = 0;
for(int i = 0; i < large.size(); i++)
sum += (int)large.get(i);
return sum;
}
// Driver code
public static void main(String args[])
{
int list[] = { -2, 8, 3, 8, -4, -15,
5, -2, -3, 1 };
int N = (list.length);
System.out.print(calculateMaxSum(N, list));
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 implementation to find the # longest alternating subsequence # which has the maximum sum def calculateMaxSum(n, li): # Creating a temporary list ar to every # time store same sign element to # calculate maximum element from # that list ar ar =[] # Appending 1st element of list li # to the ar ar.append(li[0]) # Creating list to store maximum # values large =[] for j in range(0, n-1): # If both number are positive # then append (j + 1)th element # to temporary list ar if(li[j]>0 and li[j + 1]>0): ar.append(li[j + 1]) elif(li[j]>0 and li[j + 1]<0): # If opposite elements found # then append maximum element # to large list large.append(max(ar)) # Empty ar list to re-append # next elements ar =[] ar.append(li[j + 1]) elif(li[j]<0 and li[j + 1]>0): # If opposite elements found # then append maximum element # to large list large.append(max(ar)) # Empty ar list to re-append # next elements ar =[] ar.append(li[j + 1]) else: # If both number are negative # then append (j + 1)th element # to temporary list ar ar.append(li[j + 1]) # The final Maximum element in ar list # also needs to be appended to large list large.append(max(ar)) # returning the sum of all elements # from largest elements list with # largest alternating subsequence size return sum(large) # Driver code list =[-2, 8, 3, 8, -4, -15, 5, -2, -3, 1] N = len(list) print(calculateMaxSum(N, list))
C#
// C# implementation to find the
// longest alternating subsequence
// which has the maximum sum
using System;
using System.Collections.Generic;
class GFG{
static int find_max(List<int> ar)
{
int mx = -1000000;
foreach(var i in ar)
{
if(i > mx)
mx = i;
}
return mx;
}
static int calculateMaxSum(int n, int []li)
{
// Creating a temporary list ar to
// every time store same sign element
// to calculate maximum element from
// that list ar
List<int> ar = new List<int>();
// Appending 1st element of list li
// to the ar
ar.Add(li[0]);
// Creating list to store maximum
// values
List<int> large = new List<int>();
for(int j = 0; j < n - 1; j++)
{
// If both number are positive
// then append (j + 1)th element
// to temporary list ar
if(li[j] > 0 && li[j + 1] > 0)
{
ar.Add(li[j + 1]);
}
else if(li[j] > 0 && li[j + 1] < 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.Add(find_max(ar));
// Empty ar list to re-append
// next elements
ar.Clear();
ar.Add(li[j + 1]);
}
else if(li[j] < 0 && li[j + 1] > 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.Add(find_max(ar));
// Empty ar list to re-append
// next elements
ar.Clear();
ar.Add(li[j + 1]);
}
else
{
// If both number are negative
// then append (j + 1)th element
// to temporary list ar
ar.Add(li[j + 1]);
}
}
// The final Maximum element in ar list
// also needs to be appended to large list
large.Add(find_max(ar));
// Returning the sum of all elements
// from largest elements list with
// largest alternating subsequence size
int sum = 0;
foreach(var i in large)
{
sum += i;
}
return sum;
}
// Driver code
public static void Main()
{
int []list = { -2, 8, 3, 8, -4, -15,
5, -2, -3, 1 };
int N = (list.Length);
Console.WriteLine(calculateMaxSum(N, list));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript implementation to find the
// longest alternating subsequence
// which has the maximum sum
function find_max(ar)
{
let mx = -1000000;
for(let i = 0; i < ar.length; i++)
{
if(ar[i] > mx)
mx = ar[i];
}
return mx;
}
function calculateMaxSum(n, li)
{
// Creating a temporary list ar to
// every time store same sign element
// to calculate maximum element from
// that list ar
let ar = [];
// Appending 1st element of list li
// to the ar
ar.push(li[0]);
// Creating list to store maximum
// values
let large = [];
for(let j = 0; j < n - 1; j++)
{
// If both number are positive
// then append (j + 1)th element
// to temporary list ar
if(li[j] > 0 && li[j + 1] > 0)
{
ar.push(li[j + 1]);
}
else if(li[j] > 0 && li[j + 1] < 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.push(find_max(ar));
// Empty ar list to re-append
// next elements
ar = [];
ar.push(li[j + 1]);
}
else if(li[j] < 0 && li[j + 1] > 0)
{
// If opposite elements found
// then append maximum element
// to large list
large.push(find_max(ar));
// Empty ar list to re-append
// next elements
ar = [];
ar.push(li[j + 1]);
}
else
{
// If both number are negative
// then append (j + 1)th element
// to temporary list ar
ar.push(li[j + 1]);
}
}
// The final Maximum element in ar list
// also needs to be appended to large list
large.push(find_max(ar));
// Returning the sum of all elements
// from largest elements list with
// largest alternating subsequence size
let sum = 0;
for(let i = 0; i < large.length; i++)
{
sum += large[i];
}
return sum;
}
let list = [ -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 ];
let N = (list.length);
document.write(calculateMaxSum(N, list));
</script>
Producción:
6
Complejidad de tiempo: O(N)