Contar subarreglos con elementos consecutivos estrictamente decrecientes

Dada una array arr[] que contiene números enteros. La tarea es encontrar el número de subarreglos decrecientes con una diferencia de 1 . 

Ejemplos: 

Entrada: arr[] = {3, 2, 1, 4}
Salida: 7
Explicación: Los siguientes son los posibles subarreglos decrecientes con diferencia 1. 
[3], [2], [1], [4], [3,2 ], [2,1] y [3,2,1]
Por lo tanto, la respuesta es 7. 

Entrada: arr[] = {5, 4, 3, 2, 1, 6}
Salida: 16

Enfoque ingenuo: este problema se puede resolver utilizando la programación dinámica . Siga los pasos a continuación para resolver el problema dado.

1. Para cada índice i, la tarea es calcular el número de subarreglos que terminan en i que sigue este patrón arr[i-2]==arr[i-1]+1 , arr[i-1]==arr[i]+1 .
2. Inicialice una variable, digamos ans = 0 , para almacenar el número de subarreglos decrecientes con una diferencia de 1 .
3. Podemos hacer una array dp[] que almacene el recuento de estos elementos continuos para cada índice.
4. dp[i] es el número de subarreglos que terminan en i que sigue este patrón.
5. Atraviese dp[] y agregue cada valor en ans.
6. Devuelve ans como el resultado final.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of
// decreasing subarrays with difference 1
long long getcount(vector<int>& p)
{
    int size = p.size(), cnt = 0;
    long long ans = 0;
    vector<int> dp(size, cnt);
    for (int i = 0; i < size; i++) {
        if (i == 0)
            cnt = 1;
        else if (p[i] + 1 == p[i - 1])
            cnt++;
        else
            cnt = 1;
        dp[i] = cnt;
    }
    for (int i = 0; i < size; i++)
        ans += dp[i];
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr{ 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    cout << getcount(arr);
 
    return 0;
}

// Java code to implement the above approach
import java.util.*;
public class GFG
{
 
  // Function to count number of
  // decreasing subarrays with difference 1
  static long getcount(int p[])
  {
    int size = p.length, cnt = 0;
    long ans = 0;
 
    int dp[] = new int[size];
    for(int i = 0; i < size; i++) {
      dp[i] = cnt;
    }
 
    for (int i = 0; i < size; i++) {
      if (i == 0)
        cnt = 1;
      else if (p[i] + 1 == p[i - 1])
        cnt++;
      else
        cnt = 1;
      dp[i] = cnt;
    }
    for (int i = 0; i < size; i++)
      ans += dp[i];
    return ans;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int arr[] = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    System.out.println(getcount(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code to implement the above approach
 
# Function to count number of
# decreasing subarrays with difference 1
def getcount(p):
    size = len(p)
    cnt = 0
    ans = 0
    dp = [cnt for i in range(size)]
    for i in range(size):
        if (i == 0):
            cnt = 1
        elif (p[i] + 1 == p[i - 1]):
            cnt += 1
        else:
            cnt = 1
        dp[i] = cnt
         
    for i in range(size):
        ans += dp[i]
    return ans
 
# Driver Code
arr = [5, 4, 3, 2, 1, 6]
 
# Function Call
print(getcount(arr))
 
# This code is contributed by Shubham Singh

// C# code to implement the above approach
using System;
class GFG
{
   
  // Function to count number of
  // decreasing subarrays with difference 1
  static long getcount(int []p)
  {
    int size = p.Length, cnt = 0;
    long ans = 0;
 
    int []dp = new int[size];
    for(int i = 0; i < size; i++) {
      dp[i] = cnt;
    }
 
    for (int i = 0; i < size; i++) {
      if (i == 0)
        cnt = 1;
      else if (p[i] + 1 == p[i - 1])
        cnt++;
      else
        cnt = 1;
      dp[i] = cnt;
    }
    for (int i = 0; i < size; i++)
      ans += dp[i];
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int []arr = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    Console.Write(getcount(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript program for above approach
 
// Function to count number of decreasing
// subarrays with difference 1
function getcount(p)
{
    let size = p.length, cnt = 0;
    let ans = 0;
    let dp = new Array(size).fill(cnt);
     
    for(let i = 0; i < size; i++)
    {
        if (i == 0)
            cnt = 1;
        else if (p[i] + 1 == p[i - 1])
            cnt++;
        else
            cnt = 1;
             
        dp[i] = cnt;
    }
    for(let i = 0; i < size; i++)
        ans += dp[i];
         
    return ans;
}
 
// Driver Code
let arr = [ 5, 4, 3, 2, 1, 6 ];
 
// Function Call
document.write(getcount(arr));
 
// This code is contributed by Potta Lokesh
 
</script>

16

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

Enfoque eficiente: en el enfoque anterior, la complejidad del espacio auxiliar se puede optimizar aún más a un espacio constante reemplazando la array dp[] con una variable para realizar un seguimiento del número actual de subarreglos. Siga los pasos a continuación para resolver el problema dado.

• Inicialice una variable, digamos count = 0 .
• Comience a recorrer la array cuando arr[i]-arr[i-1 ]==1 para hacer una string de números que disminuyen en 1 , luego count++ .
• Agregue el conteo a la ans.
• Cuando la string se rompe, eso significa, arr[i]-arr[i-1] !=1 luego reinicia el conteo.
• Devuelve ans como el resultado final.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// decreasing subarrays with difference 1
long long getcount(vector<int>& arr)
{
    long long int ans = arr.size();
    long long int count = 0;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i - 1] - arr[i] == 1)
            count++;
        else
            count = 0;
        ans = ans + count;
    }
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr{ 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    cout << getcount(arr);
 
    return 0;
}

// Java program for above approach
class GFG
{
 
  // Function to count the number of
  // decreasing subarrays with difference 1
  static long getcount(int[] arr)
  {
    int ans = arr.length;
    int count = 0;
    for (int i = 1; i < arr.length; i++) {
      if (arr[i - 1] - arr[i] == 1)
        count++;
      else
        count = 0;
      ans = ans + count;
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    System.out.print(getcount(arr));
 
  }
}
 
// This code is contributed by 29AjayKumar

#Python program for the above approach
 
# Function to count the number of
# decreasing subarrays with difference 1
def getcount(arr):
    ans = len(arr)
    count = 0
    for i in range(1, len(arr)):
        if (arr[i - 1] - arr[i] == 1):
            count+=1
        else:
            count = 0
        ans = ans + count
         
    return ans
 
  # Driver Code
arr = [ 5, 4, 3, 2, 1, 6 ]
 
# Function Call
print(getcount(arr))
 
# This code is contributed by Shubham Singh

// C# program for above approach
using System;
 
public class GFG
{
 
  // Function to count the number of
  // decreasing subarrays with difference 1
  static long getcount(int[] arr)
  {
    int ans = arr.Length;
    int count = 0;
    for (int i = 1; i < arr.Length; i++) {
      if (arr[i - 1] - arr[i] == 1)
        count++;
      else
        count = 0;
      ans = ans + count;
    }
    return ans;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] arr = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    Console.Write(getcount(arr));
 
  }
}
 
// This code is contributed by 29AjayKumar

<script>
// javascript program for above approach
 
// Function to count the number of
  // decreasing subarrays with difference 1
  function getcount(arr)
  {
    var ans = arr.length;
    var count = 0;
    for (var i = 1; i < arr.length; i++) {
      if (arr[i - 1] - arr[i] == 1)
        count++;
      else
        count = 0;
      ans = ans + count;
    }
    return ans;
  }
 
  // Driver Code
var arr = [ 5, 4, 3, 2, 1, 6 ];
 
// Function Call
document.write(getcount(arr));
 
// This code is contributed by 29AjayKumar
</script>

16

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