Dada una array, la tarea es encontrar la suma de la subsecuencia alterna de suma máxima que comienza con el primer elemento. Aquí secuencia alternante significa primero decreciente, luego creciente, luego decreciente… Por ejemplo, 10, 5, 14, 3 es una secuencia alterna.
Tenga en cuenta que el tipo de secuencia inversa (creciente – decreciente – creciente -…) no se considera alternante aquí.
Ejemplos:
Input : arr[] = {4, 3, 8, 5, 3, 8}
Output : 28
Explanation:
The alternating subsequence (starting with first element)
that has above maximum sum is {4, 3, 8, 5, 8}
Input : arr[] = {4, 8, 2, 5, 6, 8}
Output : 14
The alternating subsequence (starting with first element)
that has above maximum sum is {4, 2, 8}
Este problema es similar al problema de la subsecuencia creciente más larga (LIS). y se puede resolver usando Programación Dinámica.
Create two empty array that store result of maximum
sum of alternate sub-sequence
inc[] : inc[i] stores results of maximum sum alternating
subsequence ending with arr[i] such that arr[i]
is greater than previous element of the subsequence
dec[] : dec[i] stores results of maximum sum alternating
subsequence ending with arr[i] such that arr[i]
is less than previous element of the subsequence
Include first element of 'arr' in both inc[] and dec[]
inc[0] = dec[0] = arr[0]
// Maintain a flag i.e. it will makes the greater
// elements count only if the first decreasing element
// is counted.
flag = 0
Traversal two loops
i goes from 1 to n-1
j goes 0 to i-1
IF arr[j] > arr[i]
dec[i] = max(dec[i], inc[j] + arr[i])
// Denotes first decreasing is found
flag = 1
ELSE IF arr[j] < arr[i] && flag == 1
inc[i] = max(inc[i], dec[j]+arr[i]);
Final Last Find maximum value inc[] and dec[] .
A continuación se muestra la implementación de la idea anterior.
Nota:- Para el caso en que el primer elemento de la array sea el elemento más pequeño de la array. La salida será solo el primer elemento. Este es un caso límite que necesita ser revisado. Tomar una variable e inicializarla con el primer valor de la array y luego compararla con otros valores encontrará el valor mínimo. Compruebe si el min es igual a arr[0]. Si es cierto, se devolverá arr[0], porque no hay un paso decreciente disponible para encontrar una subsecuencia alterna.
C++
// C++ program to find sum of maximum
// sum alternating sequence starting with
// first element.
#include <bits/stdc++.h>
using namespace std;
// Return sum of maximum sum alternating
// sequence starting with arr[0] and is first
// decreasing.
int maxAlternateSum(int arr[], int n)
{
if (n == 1)
return arr[0];
// handling the edge case
int min = arr[0];
for (int i = 1; i < n; i++) {
if (min > arr[i])
min = arr[i];
}
if (min == arr[0]) {
return arr[0];
}
// create two empty array that store result of
// maximum sum of alternate sub-sequence
// stores sum of decreasing and increasing
// sub-sequence
int dec[n];
memset(dec, 0, sizeof(dec));
// store sum of increasing and decreasing sub-sequence
int inc[n];
memset(inc, 0, sizeof(inc));
// As per question, first element must be part
// of solution.
dec[0] = inc[0] = arr[0];
int flag = 0;
// Traverse remaining elements of array
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// IF current sub-sequence is decreasing the
// update dec[j] if needed. dec[i] by current
// inc[j] + arr[i]
if (arr[j] > arr[i]) {
dec[i] = max(dec[i], inc[j] + arr[i]);
// Revert the flag , if first decreasing
// is found
flag = 1;
}
// If next element is greater but flag should be
// 1 i.e. this element should be counted after
// the first decreasing element gets counted
else if (arr[j] < arr[i] && flag == 1)
// If current sub-sequence is increasing
// then update inc[i]
inc[i] = max(inc[i], dec[j] + arr[i]);
}
}
// find maximum sum in b/w inc[] and dec[]
int result = INT_MIN;
for (int i = 0; i < n; i++) {
if (result < inc[i])
result = inc[i];
if (result < dec[i])
result = dec[i];
}
// return maximum sum alternate sub-sequence
return result;
}
// Driver program
int main()
{
int arr[] = { 8, 2, 3, 5, 7, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << maxAlternateSum(arr, n)
<< endl;
return 0;
}
Java
// Java program to find sum of maximum
// sum alternating sequence starting with
// first element.
public class GFG {
// Return sum of maximum sum alternating
// sequence starting with arr[0] and is first
// decreasing.
static int maxAlternateSum(int arr[], int n)
{
if (n == 1)
return arr[0];
// handling the edge case
int min = arr[0];
for (int i = 1; i < n; i++) {
if (min > arr[i])
min = arr[i];
}
if (min == arr[0]) {
return arr[0];
}
// create two empty array that store result of
// maximum sum of alternate sub-sequence
// stores sum of decreasing and increasing
// sub-sequence
int dec[] = new int[n];
// store sum of increasing and decreasing
// sub-sequence
int inc[] = new int[n];
// As per question, first element must be part
// of solution.
dec[0] = inc[0] = arr[0];
int flag = 0;
// Traverse remaining elements of array
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// IF current sub-sequence is decreasing the
// update dec[j] if needed. dec[i] by
// current inc[j] + arr[i]
if (arr[j] > arr[i]) {
dec[i]
= Math.max(dec[i], inc[j] + arr[i]);
// Revert the flag , if first decreasing
// is found
flag = 1;
}
// If next element is greater but flag
// should be 1 i.e. this element should be
// counted after the first decreasing
// element gets counted
else if (arr[j] < arr[i] && flag == 1)
// If current sub-sequence is increasing
// then update inc[i]
inc[i]
= Math.max(inc[i], dec[j] + arr[i]);
}
}
// find maximum sum in b/w inc[] and dec[]
int result = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (result < inc[i])
result = inc[i];
if (result < dec[i])
result = dec[i];
}
// return maximum sum alternate sub-sequence
return result;
}
// Driver Method
public static void main(String[] args)
{
int arr[] = { 8, 2, 3, 5, 7, 9, 10 };
System.out.println(
"Maximum sum = "
+ maxAlternateSum(arr, arr.length));
}
}
Python3
# Python3 program to find sum of maximum
# sum alternating sequence starting with
# first element.
# Return sum of maximum sum alternating
# sequence starting with arr[0] and is
# first decreasing.
def maxAlternateSum(arr, n):
if (n == 1):
return arr[0]
min = arr[0]
for i in range(1, n):
if(min > arr[i]):
min = arr[i]
if(arr[0] == min):
return arr[0]
# Create two empty array that
# store result of maximum sum
# of alternate sub-sequence
# Stores sum of decreasing and
# increasing sub-sequence
dec = [0 for i in range(n + 1)]
# store sum of increasing and
# decreasing sub-sequence
inc = [0 for i in range(n + 1)]
# As per question, first element
# must be part of solution.
dec[0] = inc[0] = arr[0]
flag = 0
# Traverse remaining elements of array
for i in range(1, n):
for j in range(i):
# IF current sub-sequence is decreasing the
# update dec[j] if needed. dec[i] by current
# inc[j] + arr[i]
if (arr[j] > arr[i]):
dec[i] = max(dec[i], inc[j] + arr[i])
# Revert the flag, if first
# decreasing is found
flag = 1
# If next element is greater but flag should be 1
# i.e. this element should be counted after the
# first decreasing element gets counted
else if (arr[j] < arr[i] and flag == 1):
# If current sub-sequence is
# increasing then update inc[i]
inc[i] = max(inc[i], dec[j] + arr[i])
# Find maximum sum in b/w inc[] and dec[]
result = -2147483648
for i in range(n):
if (result < inc[i]):
result = inc[i]
if (result < dec[i]):
result = dec[i]
# Return maximum sum
# alternate sub-sequence
return result
# Driver program
arr = [8, 2, 3, 5, 7, 9, 10]
n = len(arr)
print("Maximum sum = ",
maxAlternateSum(arr, n))
# This code is contributed by Anant Agarwal.
C#
// C# program to find sum of maximum
// sum alternating sequence starting with
// first element.
using System;
class GFG {
// Return sum of maximum
// sum alternating
// sequence starting with
// arr[0] and is first
// decreasing.
static int maxAlternateSum(int[] arr, int n)
{
if (n == 1)
return arr[0];
// handling the edge case
int min = arr[0];
for (int i = 1; i < n; i++) {
if (min > arr[i])
min = arr[i];
}
if (min == arr[0]) {
return arr[0];
}
// create two empty array that
// store result of maximum sum
// of alternate sub-sequence
// stores sum of decreasing
// and increasing sub-sequence
int[] dec = new int[n];
// store sum of increasing and
// decreasing sub-sequence
int[] inc = new int[n];
// As per question, first
// element must be part
// of solution.
dec[0] = inc[0] = arr[0];
int flag = 0;
// Traverse remaining elements of array
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// IF current sub-sequence
// is decreasing the
// update dec[j] if needed.
// dec[i] by current
// inc[j] + arr[i]
if (arr[j] > arr[i]) {
dec[i]
= Math.Max(dec[i], inc[j] + arr[i]);
// Revert the flag , if
// first decreasing
// is found
flag = 1;
}
// If next element is greater
// but flag should be 1
// i.e. this element should
// be counted after the
// first decreasing element
// gets counted
else if (arr[j] < arr[i] && flag == 1)
// If current sub-sequence
// is increasing then update
// inc[i]
inc[i]
= Math.Max(inc[i], dec[j] + arr[i]);
}
}
// find maximum sum in b/w
// inc[] and dec[]
int result = int.MinValue;
for (int i = 0; i < n; i++) {
if (result < inc[i])
result = inc[i];
if (result < dec[i])
result = dec[i];
}
// return maximum sum
// alternate sub-sequence
return result;
}
// Driver Method
public static void Main()
{
int[] arr = { 8, 2, 3, 5, 7, 9, 10 };
Console.Write("Maximum sum = "
+ maxAlternateSum(arr, arr.Length));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find sum of maximum
// sum alternating sequence starting
// with first element.
// Return sum of maximum sum alternating
// sequence starting with arr[0] and is
// first decreasing.
function maxAlternateSum($arr, $n)
{
if ($n == 1)
return $arr[0];
$min = $arr[0];
for ($i = 1; $i < $n; $i++)
{ $min = max($min,$arr[$i]);}
if($arr[0]==$min)
return $arr[0];
// create two empty array that store result
// of maximum sum of alternate sub-sequence
// stores sum of decreasing and
// increasing sub-sequence
$dec = array_fill(0, $n, 0);
// store sum of increasing and
// decreasing sub-sequence
$inc = array_fill(0, $n, 0);
// As per question, first element
// must be part of solution.
$dec[0] = $inc[0] = $arr[0];
$flag = 0;
// Traverse remaining elements of array
for ($i = 1; $i < $n; $i++)
{
for ($j = 0; $j < $i; $j++)
{
// IF current sub-sequence is decreasing
// the update dec[j] if needed. dec[i]
// by current inc[j] + arr[i]
if ($arr[$j] > $arr[$i])
{
$dec[$i] = max($dec[$i], $inc[$j] +
$arr[$i]);
// Revert the flag , if first
// decreasing is found
$flag = 1;
}
// If next element is greater but flag
// should be 1 i.e. this element should
// be counted after the first decreasing
// element gets counted
else if ($arr[$j] < $arr[$i] && $flag == 1)
// If current sub-sequence is increasing
// then update inc[i]
$inc[$i] = max($inc[$i], $dec[$j] +
$arr[$i]);
}
}
// find maximum sum in b/w inc[] and dec[]
$result = -(PHP_INT_MAX - 1);
for ($i = 0 ; $i < $n; $i++)
{
if ($result < $inc[$i])
$result = $inc[$i];
if ($result < $dec[$i])
$result = $dec[$i];
}
// return maximum sum alternate sub-sequence
return $result;
}
// Driver Code
$arr = array(8, 2, 3, 5, 7, 9, 10);
$n = sizeof($arr);
echo "Maximum sum = ",
maxAlternateSum($arr, $n );
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to find sum of maximum
// sum alternating sequence starting with
// first element.
// Return sum of maximum sum alternating
// sequence starting with arr[0] and is first
// decreasing.
function maxAlternateSum(arr, n)
{
if (n == 1)
return arr[0];
//handling the edge case
int min = arr[0];
for (int i=1; i<n; i++){
if (min>arr[i])
min = arr[i];
}
if (min==arr[0]){
return arr[0];
}
// create two empty array that store result of
// maximum sum of alternate sub-sequence
// stores sum of decreasing and increasing
// sub-sequence
let dec = new Array(n);
dec.fill(0);
// store sum of increasing and decreasing sub-sequence
let inc = new Array(n);
inc.fill(0);
// As per question, first element must be part
// of solution.
dec[0] = inc[0] = arr[0];
let flag = 0 ;
// Traverse remaining elements of array
for (let i=1; i<n; i++)
{
for (let j=0; j<i; j++)
{
// IF current sub-sequence is decreasing the
// update dec[j] if needed. dec[i] by current
// inc[j] + arr[i]
if (arr[j] > arr[i])
{
dec[i] = Math.max(dec[i], inc[j]+arr[i]);
// Revert the flag , if first decreasing
// is found
flag = 1;
}
// If next element is greater but flag should be 1
// i.e. this element should be counted after the
// first decreasing element gets counted
else if (arr[j] < arr[i] && flag == 1)
// If current sub-sequence is increasing
// then update inc[i]
inc[i] = Math.max(inc[i], dec[j]+arr[i]);
}
}
// find maximum sum in b/w inc[] and dec[]
let result = Number.MIN_VALUE;
for (let i = 0 ; i < n; i++)
{
if (result < inc[i])
result = inc[i];
if (result < dec[i])
result = dec[i];
}
// return maximum sum alternate sub-sequence
return result;
}
let arr = [8, 2, 3, 5, 7, 9, 10];
document.write("Maximum sum = " +
maxAlternateSum(arr , arr.length));
</script>
Producción
Maximum sum = 25
Complejidad de tiempo: O(n 2 )
Espacio auxiliar: O(n)
Este artículo es una contribución de Sahil Chhabra(KILLER) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA