Dada una array de enteros arr[] , encuentre la subsecuencia con suma máxima cuyos elementos primero disminuyen, luego aumentan o viceversa. La subsecuencia puede comenzar en cualquier parte de la secuencia principal, no necesariamente en el primer elemento de la secuencia principal.
Una secuencia {x1, x2, .. xn} es una secuencia alterna si sus elementos satisfacen una de las siguientes relaciones (como se describe en el artículo Subsecuencia alterna más larga ) :
Dos elementos adyacentes que son iguales no se cuentan como alternos .
x1 < x2 > x3 < x4 > x5 < …. xn
o
x1 > x2 < x3 > x4 < x5 > …. xn
Ejemplos:
Entrada: arr[] = {4, 8, 2, 5, 6, 8}
Salida: 26
Explicación: La subsecuencia alterna con suma máxima es {4, 8, 6, 8}. Suma = 4 + 8 + 6 + 8 = 26Entrada: arr[] = {0, 1, 1, 1, 3, 2, 5}
Salida: 11
Explicación: La subsecuencia alterna con suma máxima es {1, 3, 2, 5}. Suma = 1 + 3 + 2 + 5 = 11Entrada: arr[] = {1, 4, 5}
Salida: 9
Explicación: La subsecuencia alterna con suma máxima es {4, 5}. Suma = 4 + 5 = 9Entrada: arr[] = {1, 0, 1, 0, 0, 3}
Salida: 5
Explicación: La subsecuencia alterna con suma máxima es {1, 0, 1, 0, 3}. Suma = 1 + 0 + 1 + 0 + 3 = 5Entrada: arr[] = {5, 5}
Salida: 5
Explicación: La subsecuencia alterna con suma máxima es {5}. Suma = 5
Este problema es una extensión del problema de subsecuencias alternas de suma máxima . A diferencia del problema anterior, ahora necesitamos calcular la suma máxima de la subsecuencia alterna independientemente de dónde se encuentre en la secuencia principal , e independientemente de si comienza con dos elementos ascendentes o descendentes .
Enfoque: Este problema se puede resolver mediante Programación Dinámica combinada con Backtracking . Supongamos que tenemos una array arr[] con cualquier N elementos.
- Podemos considerar cada elemento arr[i] como un elemento terminal de una secuencia alterna.
- Puede haber muchas subsecuencias alternas cuyo último elemento sea arr[i] , pero seguramente una de ellas es la secuencia con mayor suma.
- Además, la suma máxima de las subsecuencias alternas que terminan en arr[i] no es necesariamente mayor que la suma máxima de las subsecuencias alternas que terminan en arr[i-1]. Y esta es la base para implementar el algoritmo según la técnica de Backtracking .
- Haga que una array diga maxSum[] de longitud N que almacenará todas las sumas máximas que terminan en cada elemento de la array arr[] . Específicamente, maxSum[i] almacenará la suma máxima de la subsecuencia alterna que termina en el valor arr[i].
- Usaremos otra array before[] para almacenar el valor que precede al último elemento de cada subsecuencia alterna con suma máxima.
Por ejemplo , un arreglo arr[] = {1, 5, 7, 3, 4, 5} tendrá una subsecuencia alterna {5, 7, 3, 4} cuya suma máxima es 5 + 7 + 3 + 4 = 19.
La subsecuencia {5, 7, 3, 4} termina en el valor 4, que tiene el índice 4 en el arreglo arr[].
Entonces tenemos arr[4] = 4, maxSum[4] = 19, before[4] = 3 (porque arr[3] = 3).
Esos valores se calcularán y guardarán en dos arrays maxSum[] y before[] durante el cálculo y se pueden reutilizar según sea necesario.
Use los siguientes pasos para implementar el enfoque:
- Utilice un bucle para iterar a través de cada elemento de la array arr[]. Cada vez que atravesamos un elemento arr[i], observamos los elementos que lo preceden:
i Recorrido de bucle de 1 a N-1 (no es necesario comenzar en la posición 0, porque ese es el caso base):
j Recorrido de bucle de 0 a i-1 :
- En cada estado i y j , reutilizaremos cualquier maxSum[j] con 0 <= j < i de acuerdo con el principio de Programación Dinámica:
si:
(arr[i] > arr[j] && arr[antes de [j]] > arr[j])
o
(arr[i] < arr[j] && arr[antes de [j]] < arr[j] )entonces:
suma = arr[i] + maxSuma[j]
- Si maxSum[j] no cumple la condición anterior, pueden ser dos elementos iguales . Dado que dos elementos iguales no se tratan como una secuencia alterna, solo tomamos uno de ellos.
si:
arr[i] == arr[j]entonces:
suma = maxSuma[j]
- O puede no ser ninguno de los anteriores, como tener más de dos elementos en orden creciente o tener más de dos elementos en orden decreciente.
Ejemplo {1, 5, 7, 3, 4, 5 }. Supongamos que estamos en i = 5, j = 4 .
- Entonces before[4] es el tercer elemento , y (arr[before[j]], arr[j], arr[i]) = (arr[before[4]], arr[4], arr[5 ]) = (arr[3], arr[4], arr[5]) = (3, 4, 5).
- La anterior no es una subsecuencia alterna válida , lo que significa que before[j] no es el índice de un valor válido.
- Veremos el elemento anterior de arr[before[j]] en su secuencia alterna: before[before[j]] = before[3] = 2, and arr[2] with arr[4] and arr[5] formar una subsecuencia válida (7, 4, 5).
- Entonces obtenemos un valor de arr[5] + arr[4] + maxSum[2], que es la suma final del estado {i = 5, j = 4}.
- Necesitamos compararlo con otros estados {i y j} (como {i = 5, j = 3}, {i = 5, j = 2}…) para obtener el resultado final de maxSum[5].
- Luego guarde j en before[5] si precede a arr[5] y ayuda a arr[5] a formar una subsecuencia válida con una suma máxima en el estado 5.
Eche un vistazo a la ilustración a continuación para tener una idea clara.
índice : 0 1 2 3 4 5 || N = 6
arr[] : 1, 5, 7, 3, 4, 5——————————————————————————————————-
maxSum[0] : 1 0 0 0 0 0 = 1 caso base
antes de [-1] : -1 _ _ _ _ _maxSum[1] : 1 6 0 0 0 0 = 6 porque 1 + 5
antes[1] : -1 0 _ _ _ _maxSum[2]: 1 6 12 0 0 0 = 12 porque 1, 5, 7 no es una subsecuencia alterna , y solo 5 y 7
before[2]: -1 0 1 _ _ _ es válido, usamos el retroceso en el índice 2 por
lo que pasaremos por la siguiente subsecuencia: {1, 7}, {5, 7}. Tenemos {5, 7} porque before[1] es el índice 0,
continuamos encontrando valor en before[before[1]] = -1, cuyo valor es 0, entonces 0 + 5 + 7 = 12 > 1 + 7 .maxSum[3] : 1 6 12 15 0 0 = 15 porque 5, 7, 3 es una subsecuencia alterna válida,
before[3] : -1 0 1 2 _ _ so 3 + max(maxSum[2], maxSum[1] , maxSuma[0]) = 3 + 12.maxSum[4] : 1 6 12 15 19 0 = 19 porque 5, 7, 3, 4 es una subsecuencia alterna válida,
before[4] : -1 0 1 2 3 _ entonces 4 + max(maxSum[3], maxSum[ 2],… maxSuma[0]) = 4 + 15.maxSum[5] : 1 6 12 15 19 21 = 21 , arr[5] no puede ser el siguiente elemento de maxSum[4] porque 3, 4, 5
before[5] : -1 0 1 2 3 2 no está alternando subsecuencia Así que necesitamos usar el retroceso aquí.
Trataremos el valor 3 como un valor inválido para la subsecuencia alterna que termina en arr[5].
Necesitamos encontrar el elemento anterior de before[arr[4]] en la suma de maxSum[4] recursivamente,
es decir, el índice 2. Ahora 7, 4, 5 han formado una subsecuencia alterna válida.
Entonces tenemos 5 + max(backtracking(index 4), maxSum[3], maxSum[2],…) = 5 + 16 (porque 4 + 7 + 5)
Entonces, la suma máxima final de la subsecuencia alterna de arr es el elemento max de la array «maxSum».Salida: 21
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for backtracking
int backtracking(int arr[], int maxSum[], int before[],
int N, int root, int bef_root,
int bbef_root)
{
// {root, bef_root} represents state{i, j}
// bbef_root represent before[before[j]]
// We ignore the invalid before[j] index
// Base case:
if (bbef_root == -1)
return arr[bef_root];
// The case of a subsequence with
// alternating parts:
if ((arr[root] > arr[bef_root]
&& arr[bbef_root] > arr[bef_root])
|| (arr[root] < arr[bef_root]
&& arr[bbef_root] < arr[bef_root])) {
return arr[bef_root] + maxSum[bbef_root];
}
// case (arr[bef_root] == arr[bbef_root])
else {
return backtracking(arr, maxSum, before, N, root,
bef_root, before[bbef_root]);
}
}
int maxSumAlternatingSubsequence(int arr[], int N)
{
// Max alternating subsequence sum
// ending at arr[i].
int maxSum[N];
// Array to store the index of the element
// preceding the last element at maxSum[i]
int before[N];
// Value initialization for arrays:
fill_n(&maxSum[0], N, 0);
maxSum[0] = arr[0];
before[0] = -1;
// Iterate over the array:
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++) {
int currentMax = 0;
if ((arr[i] > arr[j]
&& arr[before[j]] > arr[j])
|| (arr[i] < arr[j]
&& arr[before[j]] < arr[j])
|| before[j] == -1) {
// Whenever an element is
// between two smaller elements
// or between two larger elements,
// it is an alternating sequence.
// When the preceding index of j is -1,
// we need to treat it explicitly,
// because -1 is not a valid index.
currentMax = (arr[i] == arr[j])
? maxSum[j]
: arr[i] + maxSum[j];
}
else if (arr[i] == arr[j]) {
// If arr[i] is equal to arr[j] then
// only take it once,
// before[j] cannot be equal to -1.
currentMax = maxSum[j];
}
else {
// Perform backtracking
// If three adjacent elements
// are increasing or decreasing.
currentMax = arr[i]
+ backtracking(
arr, maxSum, before, N, i,
j, before[before[j]]);
}
if (currentMax >= maxSum[i]) {
// Stores the maximum sum and
// the index preceding
// the last element
// at position i of
// current alternating subsequence
// after each iteration.
maxSum[i] = currentMax;
before[i] = j;
}
}
// get max result in array
return *max_element(maxSum, maxSum + N);
}
// Driver code
int main()
{
int arr[] = { 1, 5, 7, 3, 4, 5 };
int N = sizeof(arr) / sizeof(int);
// Maximum sum of alternating subsequence
// of array arr[]
cout << maxSumAlternatingSubsequence(arr, N)
<< endl;
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
class GFG{
// Function for backtracking
static int backtracking(int arr[], int maxSum[],
int before[], int N, int root,
int bef_root, int bbef_root)
{
// {root, bef_root} represents state{i, j}
// bbef_root represent before[before[j]]
// We ignore the invalid before[j] index
// Base case:
if (bbef_root == -1)
return arr[bef_root];
// The case of a subsequence with
// alternating parts:
if ((arr[root] > arr[bef_root] &&
arr[bbef_root] > arr[bef_root]) ||
(arr[root] < arr[bef_root] &&
arr[bbef_root] < arr[bef_root]))
{
return arr[bef_root] + maxSum[bbef_root];
}
// case (arr[bef_root] == arr[bbef_root])
else
{
return backtracking(arr, maxSum, before, N,
root, bef_root,
before[bbef_root]);
}
}
static int maxSumAlternatingSubsequence(int arr[],
int N)
{
// Max alternating subsequence sum
// ending at arr[i].
int maxSum[] = new int[N];
// Array to store the index of the element
// preceding the last element at maxSum[i]
int before[] = new int[N];
// Value initialization for arrays:
maxSum[0] = arr[0];
before[0] = -1;
// Iterate over the array:
for(int i = 1; i < N; i++)
for(int j = 0; j < i; j++)
{
int currentMax = 0;
if ((arr[i] > arr[j] && before[j] != -1 &&
arr[before[j]] > arr[j]) ||
(arr[i] < arr[j] && before[j] != -1 &&
arr[before[j]] < arr[j]) || before[j] == -1)
{
// Whenever an element is
// between two smaller elements
// or between two larger elements,
// it is an alternating sequence.
// When the preceding index of j is -1,
// we need to treat it explicitly,
// because -1 is not a valid index.
currentMax = (arr[i] == arr[j]) ? maxSum[j] :
arr[i] + maxSum[j];
}
else if (arr[i] == arr[j])
{
// If arr[i] is equal to arr[j] then
// only take it once,
// before[j] cannot be equal to -1.
currentMax = maxSum[j];
}
else
{
// Perform backtracking
// If three adjacent elements
// are increasing or decreasing.
currentMax = arr[i] + backtracking(arr, maxSum,
before, N, i, j,
before[before[j]]);
}
if (currentMax >= maxSum[i])
{
// Stores the maximum sum and the index
// preceding the last element at position
// i of current alternating subsequence
// after each iteration.
maxSum[i] = currentMax;
before[i] = j;
}
}
// get max result in array
int maxi = 0;
for(int i = 0; i < N; i++)
{
maxi = Math.max(maxSum[i], maxi);
}
return maxi;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 5, 7, 3, 4, 5 };
int N = arr.length;
// Maximum sum of alternating subsequence
// of array arr[]
System.out.println(
maxSumAlternatingSubsequence(arr, N));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python code to implement the above approach
# Function for backtracking
def backtracking(arr, maxSum, before, N, root, bef_root, bbef_root):
# {root, bef_root} represents state{i, j}
# bbef_root represent before[before[j]]
# We ignore the invalid before[j] index
# Base case:
if (bbef_root == -1):
return arr[bef_root]
# The case of a subsequence with
# alternating parts:
if (arr[root] > arr[bef_root] and arr[bbef_root] > arr[bef_root]) or (arr[root] < arr[bef_root] and arr[bbef_root] < arr[bef_root]):
return arr[bef_root] + maxSum[bbef_root]
# case (arr[bef_root] == arr[bbef_root])
else:
return backtracking(arr, maxSum, before, N,
root, bef_root,
before[bbef_root])
def maxSumAlternatingSubsequence(arr, N):
# Max alternating subsequence sum
# ending at arr[i].
maxSum = [0] * N
# Array to store the index of the element
# preceding the last element at maxSum[i]
before = [0] * N
# Value initialization for arrays:
maxSum[0] = arr[0]
before[0] = -1
# Iterate over the array:
for i in range(N):
for j in range(i):
currentMax = 0
if (arr[i] > arr[j] and before[j] != -1 and arr[before[j]] > arr[j]) or (arr[i] < arr[j] and before[j] != -1 and arr[before[j]] < arr[j]) or before[j] == -1:
# Whenever an element is
# between two smaller elements
# or between two larger elements,
# it is an alternating sequence.
# When the preceding index of j is -1,
# we need to treat it explicitly,
# because -1 is not a valid index.
currentMax = maxSum[j] if (
arr[i] == arr[j]) else arr[i] + maxSum[j]
elif (arr[i] == arr[j]):
# If arr[i] is equal to arr[j] then
# only take it once,
# before[j] cannot be equal to -1.
currentMax = maxSum[j]
else:
# Perform backtracking
# If three adjacent elements
# are increasing or decreasing.
currentMax = arr[i] + backtracking(arr, maxSum,
before, N, i, j,
before[before[j]])
if (currentMax >= maxSum[i]):
# Stores the maximum sum and the index
# preceding the last element at position
# i of current alternating subsequence
# after each iteration.
maxSum[i] = currentMax
before[i] = j
# get max result in array
maxi = 0
for i in range(N):
maxi = max(maxSum[i], maxi)
return maxi
# Driver code
arr = [1, 5, 7, 3, 4, 5]
N = len(arr)
# Maximum sum of alternating subsequence
# of array arr
print(maxSumAlternatingSubsequence(arr, N))
# This code is contributed by gfgking
C#
// C# program for above approach
using System;
class GFG{
// Function for backtracking
static int backtracking(int []arr, int []maxSum,
int []before, int N, int root,
int bef_root, int bbef_root)
{
// {root, bef_root} represents state{i, j}
// bbef_root represent before[before[j]]
// We ignore the invalid before[j] index
// Base case:
if (bbef_root == -1)
return arr[bef_root];
// The case of a subsequence with
// alternating parts:
if ((arr[root] > arr[bef_root] &&
arr[bbef_root] > arr[bef_root]) ||
(arr[root] < arr[bef_root] &&
arr[bbef_root] < arr[bef_root]))
{
return arr[bef_root] + maxSum[bbef_root];
}
// case (arr[bef_root] == arr[bbef_root])
else
{
return backtracking(arr, maxSum, before, N,
root, bef_root,
before[bbef_root]);
}
}
static int maxSumAlternatingSubsequence(int []arr,
int N)
{
// Max alternating subsequence sum
// ending at arr[i].
int []maxSum = new int[N];
// Array to store the index of the element
// preceding the last element at maxSum[i]
int []before = new int[N];
// Value initialization for arrays:
maxSum[0] = arr[0];
before[0] = -1;
// Iterate over the array:
for(int i = 1; i < N; i++)
for(int j = 0; j < i; j++)
{
int currentMax = 0;
if ((arr[i] > arr[j] && before[j] != -1 &&
arr[before[j]] > arr[j]) ||
(arr[i] < arr[j] && before[j] != -1 &&
arr[before[j]] < arr[j]) || before[j] == -1)
{
// Whenever an element is
// between two smaller elements
// or between two larger elements,
// it is an alternating sequence.
// When the preceding index of j is -1,
// we need to treat it explicitly,
// because -1 is not a valid index.
currentMax = (arr[i] == arr[j]) ? maxSum[j] :
arr[i] + maxSum[j];
}
else if (arr[i] == arr[j])
{
// If arr[i] is equal to arr[j] then
// only take it once,
// before[j] cannot be equal to -1.
currentMax = maxSum[j];
}
else
{
// Perform backtracking
// If three adjacent elements
// are increasing or decreasing.
currentMax = arr[i] + backtracking(arr, maxSum,
before, N, i, j,
before[before[j]]);
}
if (currentMax >= maxSum[i])
{
// Stores the maximum sum and the index
// preceding the last element at position
// i of current alternating subsequence
// after each iteration.
maxSum[i] = currentMax;
before[i] = j;
}
}
// get max result in array
int maxi = 0;
for(int i = 0; i < N; i++)
{
maxi = Math.Max(maxSum[i], maxi);
}
return maxi;
}
// Driver Code
public static void Main()
{
int []arr = { 1, 5, 7, 3, 4, 5 };
int N = arr.Length;
// Maximum sum of alternating subsequence
// of array arr[]
Console.Write(
maxSumAlternatingSubsequence(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// javascript code to implement the above approach
// Function for backtracking
function backtracking(arr , maxSum, before , N , root, bef_root , bbef_root)
{
// {root, bef_root} represents state{i, j}
// bbef_root represent before[before[j]]
// We ignore the invalid before[j] index
// Base case:
if (bbef_root == -1)
return arr[bef_root];
// The case of a subsequence with
// alternating parts:
if ((arr[root] > arr[bef_root] &&
arr[bbef_root] > arr[bef_root]) ||
(arr[root] < arr[bef_root] &&
arr[bbef_root] < arr[bef_root]))
{
return arr[bef_root] + maxSum[bbef_root];
}
// case (arr[bef_root] == arr[bbef_root])
else
{
return backtracking(arr, maxSum, before, N,
root, bef_root,
before[bbef_root]);
}
}
function maxSumAlternatingSubsequence(arr,N)
{
// Max alternating subsequence sum
// ending at arr[i].
var maxSum = Array.from({length: N}, (_, i) => 0);
// Array to store the index of the element
// preceding the last element at maxSum[i]
var before = Array.from({length: N}, (_, i) => 0);
// Value initialization for arrays:
maxSum[0] = arr[0];
before[0] = -1;
// Iterate over the array:
for(var i = 1; i < N; i++)
for(var j = 0; j < i; j++)
{
var currentMax = 0;
if ((arr[i] > arr[j] && before[j] != -1 &&
arr[before[j]] > arr[j]) ||
(arr[i] < arr[j] && before[j] != -1 &&
arr[before[j]] < arr[j]) || before[j] == -1)
{
// Whenever an element is
// between two smaller elements
// or between two larger elements,
// it is an alternating sequence.
// When the preceding index of j is -1,
// we need to treat it explicitly,
// because -1 is not a valid index.
currentMax = (arr[i] == arr[j]) ? maxSum[j] :
arr[i] + maxSum[j];
}
else if (arr[i] == arr[j])
{
// If arr[i] is equal to arr[j] then
// only take it once,
// before[j] cannot be equal to -1.
currentMax = maxSum[j];
}
else
{
// Perform backtracking
// If three adjacent elements
// are increasing or decreasing.
currentMax = arr[i] + backtracking(arr, maxSum,
before, N, i, j,
before[before[j]]);
}
if (currentMax >= maxSum[i])
{
// Stores the maximum sum and the index
// preceding the last element at position
// i of current alternating subsequence
// after each iteration.
maxSum[i] = currentMax;
before[i] = j;
}
}
// get max result in array
var maxi = 0;
for(var i = 0; i < N; i++)
{
maxi = Math.max(maxSum[i], maxi);
}
return maxi;
}
// Driver code
var arr = [ 1, 5, 7, 3, 4, 5 ];
var N = arr.length;
// Maximum sum of alternating subsequence
// of array arr
document.write(
maxSumAlternatingSubsequence(arr, N));
// This code is contributed by 29AjayKumar
</script>
21
Complejidad de tiempo : O(N 2 ) donde N es la longitud de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nguyenhanhkhoa01012000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA