Longitud máxima Subsecuencia con alternancia de signo y Suma máxima

Dada una array arr[] de tamaño n que tiene enteros positivos y negativos excepto cero. La tarea es encontrar la subsecuencia con un signo alterno que tenga el tamaño máximo y la suma máxima, es decir, en una subsecuencia, el signo de cada elemento adyacente es opuesto, por ejemplo, si el primero es positivo, el segundo tiene que ser negativo seguido de otro positivo. entero y así sucesivamente.
Ejemplos:
 

Input: arr[] = {2, 3, 7, -6, -4}
Output: 7 -4
Explanation:
Possible subsequences are [2, -6] [2, -4] [3, -6] [3, -4] [7, -6] [7, -4].
Out of these [7, -4] has the maximum sum. 

Input: arr[] = {-4, 9, 4, 11, -5, -17, 9, -3, -5, 2}
Output: -4 11 -5 9 -3 2  

Enfoque: 
La idea principal para resolver el problema anterior es encontrar el elemento máximo de los segmentos de la array que consta del mismo signo, lo que significa que tenemos que elegir el elemento máximo entre los elementos continuos positivos y continuos negativos. Como queremos el tamaño máximo, solo tomaremos un elemento de cada segmento y también para maximizar la suma, debemos tomar el elemento máximo de cada segmento. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to find the
// subsequence with alternating sign
// having maximum size and maximum sum.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the subsequence
// with alternating sign having
// maximum size and maximum sum.
void findSubsequence(int arr[], int n)
{
    int sign[n] = { 0 };
 
    // Find whether each element
    // is positive or negative
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0)
            sign[i] = 1;
        else
            sign[i] = -1;
    }
 
    int k = 0;
    int result[n] = { 0 };
 
    // Find the required subsequence
    for (int i = 0; i < n; i++) {
 
        int cur = arr[i];
        int j = i;
 
        while (j < n && sign[i] == sign[j]) {
 
            // Find the maximum element
            // in the specified range
            cur = max(cur, arr[j]);
            ++j;
        }
 
        result[k++] = cur;
 
        i = j - 1;
    }
 
    // print the result
    for (int i = 0; i < k; i++)
        cout << result[i] << " ";
    cout << "\n";
}
 
// Driver code
int main()
{
    // array declaration
    int arr[] = { -4, 9, 4, 11, -5, -17, 9, -3, -5, 2 };
 
    // size of array
    int n = sizeof(arr) / sizeof(arr[0]);
 
    findSubsequence(arr, n);
 
    return 0;
}

// Java implementation to find the
// subsequence with alternating sign
// having maximum size and maximum sum.
class GFG{
  
// Function to find the subsequence
// with alternating sign having
// maximum size and maximum sum.
static void findSubsequence(int arr[], int n)
{
    int sign[] = new int[n];
  
    // Find whether each element
    // is positive or negative
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0)
            sign[i] = 1;
        else
            sign[i] = -1;
    }
  
    int k = 0;
    int result[] = new int[n];
  
    // Find the required subsequence
    for (int i = 0; i < n; i++) {
  
        int cur = arr[i];
        int j = i;
  
        while (j < n && sign[i] == sign[j]) {
  
            // Find the maximum element
            // in the specified range
            cur = Math.max(cur, arr[j]);
            ++j;
        }
  
        result[k++] = cur;
  
        i = j - 1;
    }
  
    // print the result
    for (int i = 0; i < k; i++)
        System.out.print(result[i]+ " ");
    System.out.print("\n");
}
  
// Driver code
public static void main(String[] args)
{
    // array declaration
    int arr[] = { -4, 9, 4, 11, -5, -17, 9, -3, -5, 2 };
  
    // size of array
    int n = arr.length;
  
    findSubsequence(arr, n);
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation to find the
# subsequence with alternating sign
# having maximum size and maximum sum.
 
# Function to find the subsequence
# with alternating sign having
# maximum size and maximum sum.
def findSubsequence(arr, n):
    sign = [0]*n
 
    # Find whether each element
    # is positive or negative
    for i in range(n):
        if (arr[i] > 0):
            sign[i] = 1
        else:
            sign[i] = -1
 
    k = 0
    result = [0]*n
 
    # Find the required subsequence
    i = 0
    while i < n:
 
        cur = arr[i]
        j = i
 
        while (j < n and sign[i] == sign[j]):
 
            # Find the maximum element
            # in the specified range
            cur = max(cur, arr[j])
            j += 1
 
        result[k] = cur
        k += 1
 
        i = j - 1
        i += 1
 
    # print the result
    for i in range(k):
        print(result[i],end=" ")
 
# Driver code
if __name__ == '__main__':
    # array declaration
    arr=[-4, 9, 4, 11, -5, -17, 9, -3, -5, 2]
 
    # size of array
    n = len(arr)
 
    findSubsequence(arr, n)
 
# This code is contributed by mohit kumar 29

// C# implementation to find the
// subsequence with alternating sign
// having maximum size and maximum sum.
using System;
 
public class GFG{
   
// Function to find the subsequence
// with alternating sign having
// maximum size and maximum sum.
static void findSubsequence(int []arr, int n)
{
    int []sign = new int[n];
   
    // Find whether each element
    // is positive or negative
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0)
            sign[i] = 1;
        else
            sign[i] = -1;
    }
   
    int k = 0;
    int []result = new int[n];
   
    // Find the required subsequence
    for (int i = 0; i < n; i++) {
   
        int cur = arr[i];
        int j = i;
   
        while (j < n && sign[i] == sign[j]) {
   
            // Find the maximum element
            // in the specified range
            cur = Math.Max(cur, arr[j]);
            ++j;
        }
   
        result[k++] = cur;
   
        i = j - 1;
    }
   
    // print the result
    for (int i = 0; i < k; i++)
        Console.Write(result[i]+ " ");
    Console.Write("\n");
}
   
// Driver code
public static void Main(String[] args)
{
    // array declaration
    int []arr = { -4, 9, 4, 11, -5, -17, 9, -3, -5, 2 };
   
    // size of array
    int n = arr.Length;
   
    findSubsequence(arr, n);
}
}
// This code contributed by Rajput-Ji

<script>
 
// Javascript implementation to find the
// subsequence with alternating sign
// having maximum size and maximum sum.
 
// Function to find the subsequence
// with alternating sign having
// maximum size and maximum sum.
function findSubsequence(arr, n)
{
    let sign = Array.from({length: n}, (_, i) => 0);
    
    // Find whether each element
    // is positive or negative
    for (let i = 0; i < n; i++)
    {
        if (arr[i] > 0)
            sign[i] = 1;
        else
            sign[i] = -1;
    }
    
    let k = 0;
    let result = Array.from({length: n}, (_, i) => 0);
    
    // Find the required subsequence
    for (let i = 0; i < n; i++) {
    
        let cur = arr[i];
        let j = i;
    
        while (j < n && sign[i] == sign[j]) {
    
            // Find the maximum element
            // in the specified range
            cur = Math.max(cur, arr[j]);
            ++j;
        }
    
        result[k++] = cur;
    
        i = j - 1;
    }
    
    // print the result
    for (let i = 0; i < k; i++)
        document.write(result[i]+ " ");
    document.write("<br/>");
}
 
// Driver Code
     
    // array declaration
    let arr = [ -4, 9, 4, 11, -5, -17, 9, -3, -5, 2 ];
    
    // size of array
    let n = arr.length;
    
    findSubsequence(arr, n);
 
// This code is contributed by sanjoy_62.
</script>

-4 11 -5 9 -3 2

Complejidad de tiempo : O(N)

Espacio Auxiliar: O(N)