Contar subarreglos con elementos en orden creciente-decreciente alternativo o viceversa

Dada una array arr[] de tamaño N , la tarea es encontrar el recuento de subarreglos con elementos en orden alternativo creciente-decreciente o viceversa . Un subarreglo { a, b, c } será válido si y solo si se satisface ( a < b > c ) o ( a > b < c ).

Ejemplos :

Entrada : arr[] = {9, 8, 7, 6, 5}
Salida : 4
Explicación : Como cada elemento es menor que el otro,  
solo considere la secuencia de longitud 2, cuatro veces: [9, 8], [8 , 7], [7, 6], [6, 5]

Entrada : arr[] = {1, 2, 1, 2, 1}
Salida : 10
Explicación : Todas las secuencias posibles son: [1, 2, 1, 2, 1], [1, 2, 1, 2], [ 2, 1, 2, 1], [1, 2, 1],  
[2, 1, 2], [1, 2, 1], [1, 2], [2, 1], [1, 2] , [2, 1]

Enfoque : la tarea se puede resolver utilizando un enfoque de ventana deslizante y conceptos matemáticos . La solución se construye siguiendo los siguientes pasos:

• Encuentre el subarreglo válido actual más largo .
• Cuando el subarreglo válido más largo actual se rompa, tome la longitud del subarreglo que era más largo y guárdelo en un arreglo.
• Reinicie la ventana desde el punto donde terminó el subarreglo más largo anterior y encuentre la siguiente ventana más larga y repita hasta que finalice el arreglo.
• La array tendrá la longitud de las subarreglas contiguas que no se superponen .
• Para cada ventana de tamaño k, que es un subarreglo válido, todas las ventanas posibles de cualquier tamaño también son subsecuencias válidas .
• Para encontrar todas las subsecuencias posibles en una ventana, si una ventana es k, entonces cuente todos los subarreglos de todos los tamaños = kx (k-1) /2
• Haga esto para cada tamaño de ventana en la array y agréguelo para contar .
• Devuelve el conteo como respuesta final.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count
// of valid subarrays
int getSubsequenceCount(vector<int>& nums)
{
 
  bool flag = false;
  vector<int> arr;
  int i = 0, j = 1;
  while (j < nums.size()) {
    if ((nums[j] > nums[j - 1] && flag != true)
        || (nums[j] < nums[j - 1] && flag != false)) {
      if (nums[j] > nums[j - 1])
        flag = true;
      else if (nums[j] < nums[j - 1])
        flag = false;
      j += 1;
    }
 
    else {
      if (j - i != 1) {
        arr.push_back(j - i);
        flag = false;
        i = j - 1;
      }
      else {
        i = j;
        j += 1;
      }
    }
  }
  if (j - i != 1)
    arr.push_back(j - i);
  int count = 0;
 
  // Number of valid subsequences
  for (int itm : arr)
    count += itm * (itm - 1) / 2;
  return count;
}
 
int main()
{
  // Driver code
  vector<int> nums = { 1, 2, 1, 2, 1 };
  cout << getSubsequenceCount(nums) << "\n";
}
 
// This code is contributed by Taranpreet

// Java program for the above approach
import java.util.ArrayList;
 
class GFG
{
 
  // Function to find the count
  // of valid subarrays
  static int getSubsequenceCount(int[] nums) {
 
    boolean flag = false;
    ArrayList<Integer> arr = new ArrayList<Integer>();
    int i = 0, j = 1;
    while (j < nums.length) {
      if ((nums[j] > nums[j - 1] && flag != true) ||
          (nums[j] < nums[j - 1] && flag != false)) {
        if (nums[j] > nums[j - 1])
          flag = true;
        else if (nums[j] < nums[j - 1])
          flag = false;
        j += 1;
      }
 
      else {
        if (j - i != 1) {
          arr.add(j - i);
          flag = false;
          i = j - 1;
        } else {
          i = j;
          j += 1;
        }
      }
    }
    if (j - i != 1)
      arr.add(j - i);
    int count = 0;
 
    // Number of valid subsequences
    for (int itm : arr)
      count += itm * (itm - 1) / 2;
    return count;
  }
 
  public static void main(String args[]) {
    // Driver code
    int[] nums = { 1, 2, 1, 2, 1 };
    System.out.println(getSubsequenceCount(nums));
  }
}
 
// This code is contributed gfgking

# Python program for the above approach
 
# Function to find the count
# of valid subarrays
def getSubsequenceCount(nums):
    flag = None
    length = 1
    arr = []
    i, j = 0, 1
    while j < len(nums):
        if(nums[j] > nums[j-1] and flag != True) \
                or (nums[j] < nums[j-1] \
                    and flag != False):
            if(nums[j] > nums[j-1]):
                flag = True
            elif(nums[j] < nums[j-1]):
                flag = False
            j += 1
        else:
            if(j-i != 1):
                arr.append(j-i)
                flag = None
                i = j-1
            else:
                i = j
                j += 1
    if(j-i != 1):
        arr.append(j-i)
    count = 0
 
    # Number of valid subsequences
    for n in arr:
        count += n*(n-1)//2
    return count
 
# Driver code
if __name__ == "__main__":
    nums = [1, 2, 1, 2, 1]
    print(getSubsequenceCount(nums))

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to find the count
  // of valid subarrays
  static int getSubsequenceCount(int[] nums) {
 
    bool flag = false;
    List<int> arr = new List<int>();
    int i = 0, j = 1;
    while (j < nums.Length) {
      if ((nums[j] > nums[j - 1] && flag != true) ||
          (nums[j] < nums[j - 1] && flag != false)) {
        if (nums[j] > nums[j - 1])
          flag = true;
        else if (nums[j] < nums[j - 1])
          flag = false;
        j += 1;
      }
 
      else {
        if (j - i != 1) {
          arr.Add(j - i);
          flag = false;
          i = j - 1;
        } else {
          i = j;
          j += 1;
        }
      }
    }
    if (j - i != 1)
      arr.Add(j - i);
    int count = 0;
 
    // Number of valid subsequences
    foreach (int itm in arr)
      count += itm * (itm - 1) / 2;
    return count;
  }
 
  static public void Main ()
  {
     
    // Driver code
    int[] nums = { 1, 2, 1, 2, 1 };
    Console.WriteLine(getSubsequenceCount(nums));
  }
}
 
// This code is contributed Shubham Singh

<script>
    // JavaScript program for the above approach
 
    // Function to find the count
    // of valid subarrays
    const getSubsequenceCount = (nums) => {
     
        let flag = 0;
        let length = 1;
        let arr = [];
        let i = 0, j = 1;
        while (j < nums.length) {
            if ((nums[j] > nums[j - 1] && flag != true) || (nums[j] < nums[j - 1] && flag != false)) {
                if (nums[j] > nums[j - 1])
                    flag = true;
                else if (nums[j] < nums[j - 1])
                    flag = false;
                j += 1;
            }
 
            else {
                if (j - i != 1) {
                    arr.push(j - i)
                    flag = false;
                    i = j - 1;
                }
                else {
                    i = j;
                    j += 1
                }
            }
        }
        if (j - i != 1)
            arr.push(j - i);
        let count = 0;
 
        // Number of valid subsequences
        for (let itm in arr)
            count += parseInt(arr[itm] * (arr[itm] - 1) / 2)
        return count;
    }
 
    // Driver code
    nums = [1, 2, 1, 2, 1];
    document.write(getSubsequenceCount(nums));
 
    // This code is contributed by rakeshsahni
 
</script>

10

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)