Recuento de pares de índices en una array cuyo producto de rango es un entero positivo

Dada una array A de enteros distintos de cero, la tarea es encontrar el número de pares (l, r) donde (l <= r) tales que A[l]*A[l+1]*A[l+2 ]….A[r] es positivo. 
Ejemplos: 
 

Entrada: A = {5, -3, 3, -1, 1} 
Salida: 7 
Explicación: 
Primer par, (1, 1) = 5 es positivo 
Segundo par, (3, 3) = 3 es positivo 
Tercer par, ( 1, 4) = 5 * -3 * 3 * -1 = 45 es positivo 
Cuarto par, (2, 4) = -3 * 3 * -1 = 9 es positivo 
Quinto par, (1, 5) = 5 * – 3 * 3 * -1 * 1 = 45 es positivo 
Sexto par, (2, 5) = -3 * 3 * -1 * 1 = 9 es positivo 
Séptimo par, (5, 5) = 1 es positivo 
Entonces, hay siete pares con producto positivo.
Entrada: A = {4, 2, -4, 3, 1, 2, -4, 3, 2, 3} 
Salida: 27 
 

Enfoque: 
La idea es verificar posibles pares de números para cada elemento de la array. 
 

• Itere a través de una array, siga los pasos a continuación para cada elemento de la array.
• Lleve un registro del número de elementos que tienen un número par de elementos negativos delante de ellos (como even_count) y el número de elementos que tienen un número impar de elementos negativos delante de ellos (como odd_count) .
• Almacene el número total de elementos negativos hasta ahora (como total_count) .
• Si total_count es par, agregue even_count a la respuesta. De lo contrario, agregue odd_count .

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

// C++ Program to find the
// count of index pairs
// in the array positive
// range product
 
#include <bits/stdc++.h>
using namespace std;
 
void positiveProduct(int arr[], int n)
{
    int even_count = 0;
    int odd_count = 0;
    int total_count = 0;
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Condition if number of
        // negative elements is even
        // then increase even_count
        if (total_count % 2 == 0)
            even_count++;
 
        // Otherwise increase odd_count
        else
            odd_count++;
 
        // Condition if current element
        // is negative
        if (arr[i] < 0)
            total_count++;
 
        // Condition if number of
        // negative elements is even
        // then add even_count
        // in answer
        if (total_count % 2 == 0)
            ans += even_count;
 
        // Otherwise add odd_count
        // in answer
        else
            ans += odd_count;
    }
 
    cout << ans << "\n";
}
 
// Driver Code
int main()
{
    int A[] = { 5, -3, 3, -1, 1 };
 
    int size = sizeof(A) / sizeof(A[0]);
 
    positiveProduct(A, size);
 
    return 0;
}

// Java program to find the count of
// index pairs in the array positive
// range product
class GFG{
     
public static void positiveProduct(int arr[],
                                   int n)
{
    int even_count = 0;
    int odd_count = 0;
    int total_count = 0;
    int ans = 0;
     
    for(int i = 0; i < n; i++)
    {
         
       // Condition if number of
       // negative elements is even
       // then increase even_count
       if (total_count % 2 == 0)
       {
           even_count++;
       }
        
       // Otherwise increase odd_count
       else
       {
           odd_count++;
       }
        
       // Condition if current element
       // is negative
       if (arr[i] < 0)
       {
           total_count++;
       }
        
       // Condition if number of
       // negative elements is even
       // then add even_count
       // in answer
       if (total_count % 2 == 0)
           ans += even_count;
            
       // Otherwise add odd_count
       // in answer
       else
           ans += odd_count;
    }
    System.out.println(ans);
     
}
 
// Driver Code   
public static void main(String[] args)
{
    int A[] = { 5, -3, 3, -1, 1 };
    int size = A.length;
     
    positiveProduct(A, size);
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to find the count
# of index pairs in the array
# positive range product
def positiveProduct(arr, n):
 
    even_count = 0
    odd_count = 0
    total_count = 0
    ans = 0
 
    for i in range(n):
 
        # Condition if number of
        # negative elements is even
        # then increase even_count
        if(total_count % 2 == 0):
            even_count += 1
 
        # Otherwise increase odd_count
        else:
            odd_count += 1
 
        # Condition if current element
        # is negative
        if(arr[i] < 0):
            total_count += 1
 
        # Condition if number of
        # negative elements is even
        # then add even_count
        # in answer
        if(total_count % 2 == 0):
            ans += even_count
 
        # Otherwise add odd_count
        # in answer
        else:
            ans += odd_count
 
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 5, -3, 3, -1, 1 ]
    size = len(A)
 
    positiveProduct(A, size)
 
# This code is contributed by Shivam Singh

// C# program to find the count of
// index pairs in the array positive
// range product
using System;
 
class GFG{
     
public static void positiveProduct(int []arr,
                                   int n)
{
    int even_count = 0;
    int odd_count = 0;
    int total_count = 0;
    int ans = 0;
     
    for(int i = 0; i < n; i++)
    {
         
       // Condition if number of
       // negative elements is even
       // then increase even_count
       if (total_count % 2 == 0)
       {
           even_count++;
       }
        
       // Otherwise increase odd_count
       else
       {
           odd_count++;
       }
        
       // Condition if current element
       // is negative
       if (arr[i] < 0)
       {
           total_count++;
       }
        
       // Condition if number of
       // negative elements is even
       // then add even_count
       // in answer
       if (total_count % 2 == 0)
           ans += even_count;
        
       // Otherwise add odd_count
       // in answer
       else
           ans += odd_count;
    }
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 5, -3, 3, -1, 1 };
    int size = A.Length;
     
    positiveProduct(A, size);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find the count of
// index pairs in the array positive
// range product
function positiveProduct(arr,n)
{
    let even_count = 0;
    let odd_count = 0;
    let total_count = 0;
    let ans = 0;
     
    for(let i = 0; i < n; i++)
    {
         
    // Condition if number of
    // negative elements is even
    // then increase even_count
    if (total_count % 2 == 0)
    {
        even_count++;
    }
         
    // Otherwise increase odd_count
    else
    {
        odd_count++;
    }
         
    // Condition if current element
    // is negative
    if (arr[i] < 0)
    {
        total_count++;
    }
         
    // Condition if number of
    // negative elements is even
    // then add even_count
    // in answer
    if (total_count % 2 == 0)
        ans += even_count;
             
    // Otherwise add odd_count
    // in answer
    else
        ans += odd_count;
    }
    document.write(ans);
     
}
 
// Driver Code   
 
    let A = [5, -3, 3, -1, 1 ];
    let size = A.length;
     
    positiveProduct(A, size);
 
 
// This code is contributed by sravan kumar Gottumukkala
 
</script>

7

Complejidad de tiempo: O(N)  
Complejidad de espacio: O(1)