Dada una array de N enteros. La tarea es contar el número de subarreglos (del tamaño de al menos uno) que no aumentan.
Ejemplos:
Input : arr[] = {1, 4, 3}
Output : 4
The possible subarrays are {1}, {4}, {3}, {4, 3}.
Input :{4, 3, 2, 1}
Output : 10
The possible subarrays are:
{4}, {3}, {2}, {1}, {4, 3}, {3, 2}, {2, 1},
{4, 3, 2}, {3, 2, 1}, {4, 3, 2, 1}.
Solución simple : una solución simple es generar todos los subarreglos posibles y, para cada subarreglo, verifique si el subarreglo no aumenta o no. La complejidad temporal de esta solución sería O(N 3 ).
Solución eficiente : una mejor solución es utilizar el hecho de que si un subarreglo arr[i:j] no es creciente, entonces los subarreglo arr[i:j+1], arr[i:j+2], .. arr[ i:n-1] no puede ser no creciente. Por lo tanto, comience a atravesar la array y, para el subarreglo actual, siga incrementando su longitud hasta que no aumente y actualice el conteo. Una vez que el subarreglo comience a aumentar, restablezca la longitud.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to count number of non
// increasing subarrays
#include <bits/stdc++.h>
using namespace std;
int countNonIncreasing(int arr[], int n)
{
// Initialize result
int cnt = 0;
// Initialize length of current non
// increasing subarray
int len = 1;
// Traverse through the array
for (int i = 0; i < n - 1; ++i) {
// If arr[i+1] is less than or equal to arr[i],
// then increment length
if (arr[i + 1] <= arr[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
int main()
{
int arr[] = { 5, 2, 3, 7, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countNonIncreasing(arr, n);
return 0;
}
Java
// Java program to count number of non
// increasing subarrays
class GFG
{
static int countNonIncreasing(int arr[], int n)
{
// Initialize result
int cnt = 0;
// Initialize length of current non
// increasing subarray
int len = 1;
// Traverse through the array
for (int i = 0; i < n - 1; ++i)
{
// If arr[i+1] is less than or equal to arr[i],
// then increment length
if (arr[i + 1] <= arr[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
public static void main(String[] args)
{
int arr[] = { 5, 2, 3, 7, 1, 1 };
int n =arr.length;
System.out.println(countNonIncreasing(arr, n));
}
}
// This code is contributed by Code_Mech
Python3
# Python3 program to count number of non # increasing subarrays def countNonIncreasing(arr, n): # Initialize result cnt = 0; # Initialize length of current # non-increasing subarray len = 1; # Traverse through the array for i in range(0, n - 1): # If arr[i+1] is less than # or equal to arr[i], # then increment length if (arr[i + 1] <= arr[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 int(cnt); # Driver code if __name__ == '__main__': arr = [5, 2, 3, 7, 1, 1]; n = len(arr); print(countNonIncreasing(arr, n)); # This code contributed by PrinciRaj1992
C#
// C# program to count number of non
// increasing subarrays
using System;
class GFG
{
static int countNonIncreasing(int []arr, int n)
{
// Initialize result
int cnt = 0;
// Initialize length of current non
// increasing subarray
int len = 1;
// Traverse through the array
for (int i = 0; i < n - 1; ++i)
{
// If arr[i+1] is less than or equal to arr[i],
// then increment length
if (arr[i + 1] <= arr[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
public static void Main(String[] args)
{
int []arr = { 5, 2, 3, 7, 1, 1 };
int n = arr.Length;
Console.Write(countNonIncreasing(arr, n));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP program to count number of non
// increasing subarrays
function countNonIncreasing($arr, $n)
{
// Initialize result
$cnt = 0;
// Initialize length of current non
// increasing subarray
$len = 1;
// Traverse through the array
for ($i = 0; $i < $n - 1; ++$i)
{
// If arr[i+1] is less than
// or equal to arr[i],
// then increment length
if ($arr[$i + 1] <= $arr[$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
$arr = array( 5, 2, 3, 7, 1, 1 );
$n = sizeof($arr);
echo countNonIncreasing($arr, $n);
// This code is contributed by akt_mit
?>
Javascript
<script>
// Javascript program to count number of non
// increasing subarrays
function countNonIncreasing(arr, n)
{
// Initialize result
var cnt = 0;
// Initialize length of current non
// increasing subarray
var len = 1;
// Traverse through the array
for(var i = 0; i < n - 1; ++i)
{
// If arr[i+1] is less than or equal
// to arr[i], then increment length
if (arr[i + 1] <= arr[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;
}
// Driver code
var arr = [ 5, 2, 3, 7, 1, 1 ];
var n = arr.length;
document.write(countNonIncreasing(arr, n));
// This code is contributed by rutvik_56
</script>
Producción
10
Complejidad Temporal: O(N), ya que allí corre un bucle de 0 a (n – 2).
Espacio Auxiliar : O(1), ya que no se ha tomado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA