Subsecuencia alterna más larga con suma máxima | conjunto 2

Dada una array arr[] de tamaño N , que consta de enteros positivos y negativos, la tarea es encontrar la subsecuencia alterna más larga (es decir, el signo de cada elemento es opuesto al de su elemento anterior) de la array dada que tiene el máximo suma.
Ejemplos: 
 

Entrada: arr[] = {-2, 10, 3, -8, -4, -1, 5, -2, -3, 1} 
Salida: 11 
Explicación: 
dado que la subsecuencia debe ser lo más larga posible y alternar , se puede seleccionar un elemento de cada uno de los siguientes subarreglos: 
{-2}, {10, 3}, {-8, -4, -1}, {5}, {-2, -3}, {1} 
Por lo tanto, seleccionar el máximo de cada uno de los subarreglos como elementos de la subsecuencia genera una subsecuencia alterna con suma máxima. 
Por lo tanto, la subsecuencia es {-2, 10, -1, 5, -2, 1} 
Por lo tanto, la suma de la subsecuencia es 11.
Entrada: arr[] = {12, 4, -5, 7, -9} 
Salida: 5 
Explicación: 
La subsecuencia más larga con la mayor suma es {12, -5, 7, -9}. 
Por lo tanto, la suma máxima es 5. 
 

Enfoque lineal usando espacio adicional: 
Consulte la subsecuencia alterna más larga que tiene la suma máxima de elementos para el enfoque lineal usando espacio adicional. 
Complejidad de Tiempo: O(N) 
Espacio Auxiliar: O(N)
Enfoque de Espacio Eficiente: 
Para resolver el problema, podemos observar lo siguiente: 
 

• Para maximizar la longitud de la subsecuencia alterna, necesitamos considerar un elemento de cada secuencia de números consecutivos de la 
   

Ilustración: 
Consideremos un arreglo arr[] = {1, 1, 2, -1, -5, 2, 1, -3} 
Las secuencias consecutivas de elementos del mismo signo son: 
{1, 1, 2}, { -1, -5}, {2, 1}, {-3} 
Por lo tanto, al seleccionar un elemento de cada una de estas secuencias, se puede obtener una subsecuencia alterna de la mayor longitud posible. 
 

• Para maximizar la suma de la subsecuencia, necesitamos seleccionar el máximo de cada subsecuencia consecutiva de elementos del mismo signo. 
   

Ilustración: 
Para el arreglo arr[] = {1, 1, 2, -1, -5, 2, 1, -3}, se observó que las secuencias consecutivas de elementos de signo son: 
{1, 1, 2}, {-1, -5}, {2, 1}, {-3} 
Por lo tanto, la subsecuencia con la suma máxima es {2, -1, 2, -3}, formada seleccionando el elemento máximo de cada una de las secuencias . 
 

 

Siga los pasos a continuación para resolver el problema de manera eficiente: 
 

• Iterar sobre la array usando Two Pointers .
• Establezca i = 0 y establezca j = i .
• Recorra la array hasta que j apunte a un índice que consta de un elemento de signo opuesto al de arr[i] . En cada recorrido, actualice el elemento máximo encontrado entre [i, j] .
• Una vez que se encuentra un elemento de signo opuesto, agregue el máximo de la secuencia [i, j) a maxsum .
• Establezca i = j y repita los dos pasos anteriores hasta que se atraviese toda la array.
• Imprime el valor final de maxsum como respuesta.

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

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the
// sign of the element
int sign(int x)
{
    if (x > 0)
        return 1;
    else
        return -1;
}
 
// Function to calculate and
// return the maximum sum of
// longest alternating subsequence
int findMaxSum(int arr[], int size)
{
    int max_sum = 0, pres, i, j;
 
    // Iterate through the array
    for (i = 0; i < size; i++) {
 
        // Stores the first element of
        // a sequence of same sign
        pres = arr[i];
        j = i;
 
        // Traverse until an element with
        // opposite sign is encountered
        while (j < size
               && sign(arr[i])
                      == sign(arr[j])) {
 
            // Update the maximum
            pres = max(pres, arr[j]);
            j++;
        }
 
        // Update the maximum sum
        max_sum = max_sum + pres;
 
        // Update i
        i = j - 1;
    }
 
    // Return the maximum sum
    return max_sum;
}
 
// Driver Code
int main()
{
    int arr[] = { -2, 8, 3, 8, -4,
                  -15, 5, -2, -3, 1 };
 
    int size = sizeof(arr)
/ sizeof(arr[0]);
 
    cout << findMaxSum(arr, size);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
    // Function to check the
    // sign of the element
    static int sign(int x)
    {
        if (x > 0)
            return 1;
        else
            return -1;
    }
 
    // Function to calculate and
    // return the maximum sum of
    // longest alternating subsequence
    static int findMaxSum(int arr[], int size)
    {
        int max_sum = 0, pres, i, j;
 
        // Iterate through the array
        for (i = 0; i < size; i++)
        {
 
            // Stores the first element of
            // a sequence of same sign
            pres = arr[i];
            j = i;
 
            // Traverse until an element with
            // opposite sign is encountered
            while (j < size &&
                   sign(arr[i]) == sign(arr[j]))
            {
 
                // Update the maximum
                pres = Math.max(pres, arr[j]);
                j++;
            }
 
            // Update the maximum sum
            max_sum = max_sum + pres;
 
            // Update i
            i = j - 1;
        }
 
        // Return the maximum sum
        return max_sum;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 };
 
        int size = arr.length;
 
        System.out.println(findMaxSum(arr, size));
    }
}
 
// This code is contributed by sapnasingh4991

# Python3 program to implement
# the above approach
 
# Function to check the
# sign of the element
def sign(x):
 
    if (x > 0):
        return 1
    else:
        return -1
 
# Function to calculate and
# return the maximum sum of
# longest alternating subsequence
def findMaxSum(arr, size):
     
    max_sum = 0
 
    # Iterate through the array
    i = 0
    while i < size:
 
        # Stores the first element of
        # a sequence of same sign
        pres = arr[i]
        j = i
 
        # Traverse until an element with
        # opposite sign is encountered
        while (j < size and
              (sign(arr[i]) == sign(arr[j]))):
 
            # Update the maximum
            pres = max(pres, arr[j])
            j += 1
 
        # Update the maximum sum
        max_sum = max_sum + pres
 
        # Update i
        i = j - 1
        i += 1
 
    # Return the maximum sum
    return max_sum
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ -2, 8, 3, 8, -4,
            -15, 5, -2, -3, 1 ]
 
    size = len(arr)
 
    print(findMaxSum(arr, size))
 
# This code is contributed by chitranayal

// C# Program to implement
// the above approach
using System;
class GFG{
 
    // Function to check the
    // sign of the element
    static int sign(int x)
    {
        if (x > 0)
            return 1;
        else
            return -1;
    }
 
    // Function to calculate and
    // return the maximum sum of
    // longest alternating subsequence
    static int findMaxSum(int []arr, int size)
    {
        int max_sum = 0, pres, i, j;
 
        // Iterate through the array
        for (i = 0; i < size; i++)
        {
 
            // Stores the first element of
            // a sequence of same sign
            pres = arr[i];
            j = i;
 
            // Traverse until an element with
            // opposite sign is encountered
            while (j < size &&
                   sign(arr[i]) == sign(arr[j]))
            {
 
                // Update the maximum
                pres = Math.Max(pres, arr[j]);
                j++;
            }
 
            // Update the maximum sum
            max_sum = max_sum + pres;
 
            // Update i
            i = j - 1;
        }
 
        // Return the maximum sum
        return max_sum;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int []arr = { -2, 8, 3, 8, -4,
                     -15, 5, -2, -3, 1 };
 
        int size = arr.Length;
 
        Console.WriteLine(findMaxSum(arr, size));
    }
}
 
// This code is contributed by gauravrajput1

<script>
// javascript program to implement
// the above approach
 
    // Function to check the
    // sign of the element
    function sign(x)
    {
        if (x > 0)
            return 1;
        else
            return -1;
    }
  
    // Function to calculate and
    // return the maximum sum of
    // longest alternating subsequence
   function findMaxSum(arr, size)
    {
        let max_sum = 0, pres, i, j;
  
        // Iterate through the array
        for (i = 0; i < size; i++)
        {
  
            // Stores the first element of
            // a sequence of same sign
            pres = arr[i];
            j = i;
  
            // Traverse until an element with
            // opposite sign is encountered
            while (j < size &&
                   sign(arr[i]) == sign(arr[j]))
            {
  
                // Update the maximum
                pres = Math.max(pres, arr[j]);
                j++;
            }
  
            // Update the maximum sum
            max_sum = max_sum + pres;
  
            // Update i
            i = j - 1;
        }
  
        // Return the maximum sum
        return max_sum;
    }
    
    // Driver Code
           
        let arr = [ -2, 8, 3, 8, -4, -15, 5, -2, -3, 1 ];
        let size = arr.length;
        document.write(findMaxSum(arr, size));
  
 // This code is contributed by avijitmondal1998.
</script>

6

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