Encuentre el recuento de subarreglos estrictamente decrecientes

Dada una array A[] de enteros. La tarea es contar el número total de subarreglos estrictamente decrecientes (con tamaño > 1).
Ejemplos : 
 

Entrada : A[] = { 100, 3, 1, 15 } 
Salida : 3 
Los subarreglos son -> { 100, 3 }, { 100, 3, 1 }, { 3, 1 } 
Entrada : A[] = { 4, 2, 2, 1 } 
Salida : 2 
 

Enfoque ingenuo: una solución simple es ejecutar dos bucles for y verificar si el subarreglo está disminuyendo o no. 
Esto se puede mejorar sabiendo que si el subarreglo arr[i:j] no es estrictamente decreciente, entonces los subarreglo arr[i:j+1], arr[i:j+2], .. arr[i:n- 1] no puede ser estrictamente decreciente.
Enfoque eficiente: en la solución anterior, contamos muchos subarreglos dos veces. Esto también se puede mejorar y la idea se basa en el hecho de que un subarreglo ordenado (decreciente) de longitud ‘len’ agrega len*(len-1)/2 al resultado.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to count number of strictly
// decreasing subarrays in O(n) time.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of strictly
// decreasing subarrays
int countDecreasing(int A[], int n)
{
    int cnt = 0; // Initialize result
 
    // Initialize length of current
    // decreasing subarray
    int len = 1;
 
    // Traverse through the array
    for (int i = 0; i < n - 1; ++i) {
        // If arr[i+1] is less than arr[i],
        // then increment length
        if (A[i + 1] < A[i])
            len++;
 
        // Else Update count and reset length
        else {
            cnt += (((len - 1) * len) / 2);
            len = 1;
        }
    }
 
    // If last length is more than 1
    if (len > 1)
        cnt += (((len - 1) * len) / 2);
 
    return cnt;
}
 
// Driver program
int main()
{
    int A[] = { 100, 3, 1, 13 };
    int n = sizeof(A) / sizeof(A[0]);
 
    cout << countDecreasing(A, n);
 
    return 0;
}

// Java program to count number of strictly
// decreasing subarrays in O(n) time.
 
import java.io.*;
 
class GFG {
 
 
// Function to count the number of strictly
// decreasing subarrays
static int countDecreasing(int A[], int n)
{
    int cnt = 0; // Initialize result
 
    // Initialize length of current
    // decreasing subarray
    int len = 1;
 
    // Traverse through the array
    for (int i = 0; i < n - 1; ++i) {
        // If arr[i+1] is less than arr[i],
        // then increment length
        if (A[i + 1] < A[i])
            len++;
 
        // Else Update count and reset length
        else {
            cnt += (((len - 1) * len) / 2);
            len = 1;
        }
    }
 
    // If last length is more than 1
    if (len > 1)
        cnt += (((len - 1) * len) / 2);
 
    return cnt;
}
 
// Driver program
    public static void main (String[] args) {
    int A[] = { 100, 3, 1, 13 };
    int n = A.length;
 
    System.out.println(countDecreasing(A, n));
    }
}
// This code is contributed by anuj_67..

# Python 3 program to count number
# of strictly decreasing subarrays
# in O(n) time.
 
# Function to count the number of
# strictly decreasing subarrays
def countDecreasing(A, n):
 
    cnt = 0 # Initialize result
 
    # Initialize length of current
    # decreasing subarray
    len = 1
 
    # Traverse through the array
    for i in range (n - 1) :
         
        # If arr[i+1] is less than arr[i],
        # then increment length
        if (A[i + 1] < A[i]):
            len += 1
 
        # Else Update count and
        # reset length
        else :
            cnt += (((len - 1) * len) // 2);
            len = 1
     
    # If last length is more than 1
    if (len > 1):
        cnt += (((len - 1) * len) // 2)
 
    return cnt
 
# Driver Code
if __name__=="__main__":
 
    A = [ 100, 3, 1, 13 ]
    n = len(A)
 
    print (countDecreasing(A, n))
 
# This code is contributed by ChitraNayal

// C# program to count number of strictly
// decreasing subarrays in O(n) time.
 
using System;
 
class GFG
{
// Function to count the number of strictly
// decreasing subarrays
static int countDecreasing(int []A, int n)
{
int cnt = 0; // Initialize result
 
// Initialize length of current
// decreasing subarray
int len = 1;
 
// Traverse through the array
for (int i = 0; i < n - 1; ++i) {
// If arr[i+1] is less than arr[i],
// then increment length
if (A[i + 1] < A[i])
len++;
 
// Else Update count and reset length
else {
cnt += (((len - 1) * len) / 2);
len = 1;
}
}
 
// If last length is more than 1
if (len > 1)
cnt += (((len - 1) * len) / 2);
 
return cnt;
}
 
// Driver code
static void Main()
{
int []A = { 100, 3, 1, 13 };
int n = A.Length ;
Console.WriteLine(countDecreasing(A, n));
}
// This code is contributed by ANKITRAI1
}

<?php
// PHP program to count number of strictly
// decreasing subarrays in O(n) time.
 
// Function to count the number of
// strictly decreasing subarrays
function countDecreasing($A, $n)
{
    $cnt = 0; // Initialize result
 
    // Initialize length of current
    // decreasing subarray
    $len = 1;
 
    // Traverse through the array
    for ($i = 0; $i < $n - 1; ++$i)
    {
        // If arr[i+1] is less than arr[i],
        // then increment length
        if ($A[$i + 1] < $A[$i])
            $len++;
 
        // Else Update count and
        // reset length
        else
        {
            $cnt += ((($len - 1) * $len) / 2);
            $len = 1;
        }
    }
 
    // If last length is more than 1
    if ($len > 1)
        $cnt += ((($len - 1) * $len) / 2);
 
    return $cnt;
}
 
// Driver Code
$A = array( 100, 3, 1, 13 );
$n = sizeof($A);
 
echo countDecreasing($A, $n);
 
// This code is contributed by mits
?>

<script>
 
// JavaScript program to count number of strictly
// decreasing subarrays in O(n) time.
 
 
// Function to count the number of strictly
// decreasing subarrays
function countDecreasing(A, n)
{
    var cnt = 0; // Initialize result
 
    // Initialize length of current
    // decreasing subarray
    var len = 1;
 
    // Traverse through the array
    for (var i = 0; i < n - 1; ++i) {
        // If arr[i+1] is less than arr[i],
        // then increment length
        if (A[i + 1] < A[i])
            len++;
 
        // Else Update count and reset length
        else {
            cnt += parseInt(((len - 1) * len) / 2);
            len = 1;
        }
    }
 
    // If last length is more than 1
    if (len > 1)
        cnt += parseInt(((len - 1) * len) / 2);
 
    return cnt;
}
 
 
    var A = [ 100, 3, 1, 13 ];
    var n = A.length;
    document.write( countDecreasing(A, n));
 
 
// This code is contributed by SoumikMondal
 
</script>

3

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)