Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el recuento de subarreglos de modo que el elemento máximo de la subarreción sea mayor que el doble del máximo de todos los demás elementos de la array .
Ejemplos:
Entrada: arr[] = {1, 6, 10, 9, 7, 3}
Salida: 4
Explicación:
A continuación se muestran los subarreglos que cumplen la condición dada:
- Considere el subarreglo {6, 10, 9, 7}. Ahora, el elemento máximo de este subarreglo es 10, que es mayor que el doble de los elementos máximos de los elementos restantes del arreglo, es decir, 2*max{1, 3} = 2*3 = 6.
- Considere el subarreglo {6, 10, 9, 7, 3}. Ahora, el elemento máximo de este subarreglo es 10, que es mayor que el doble de los elementos máximos de los elementos restantes del arreglo, es decir, 2*max{1} = 2*1 = 2.
- Considere el subarreglo {1, 6, 10, 9, 7}. Ahora, el elemento máximo de este subarreglo es 10, que es mayor que el doble de los elementos máximos de los elementos restantes del arreglo, es decir, 2*max{3} = 2*3 = 6.
- Considere el subarreglo {1, 6, 10, 9, 7, 3}. Ahora, el elemento máximo de este subarreglo es 10, que es mayor que el doble de los elementos máximos de los elementos restantes del arreglo, es decir, 2*max{} = 2*0 = 0.
Por lo tanto, el número total de subarreglos es 4.
Entrada: arr[] = {1, 10, 2, 3}
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles del arreglo dado arr[] y luego contar el número de subarreglos que tienen un elemento máximo mayor que el doble del máximo de todos los demás elementos. Después de verificar todos los subarreglos, imprima el recuento del subarreglo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
void countSubarray(int arr[], int n)
{
// Stores the count of subarrays
int count = 0;
// Generate all possible subarrays
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Stores the maximum element
// of the subarray
int mxSubarray = 0;
// Stores the maximum of all
// other elements
int mxOther = 0;
// Find the maximum element
// in the subarray [i, j]
for (int k = i; k <= j; k++) {
mxSubarray = max(mxSubarray,
arr[k]);
}
// Find the maximum of all
// other elements
for (int k = 0; k < i; k++) {
mxOther = max(
mxOther, arr[k]);
}
for (int k = j + 1; k < n; k++) {
mxOther = max(
mxOther, arr[k]);
}
// If the maximum of subarray
// is greater than twice the
// maximum of other elements
if (mxSubarray > (2 * mxOther))
count++;
}
}
// Print the maximum value obtained
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 1, 6, 10, 9, 7, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
countSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
public static void countSubarray(int arr[], int n)
{
// Stores the count of subarrays
int count = 0;
// Generate all possible subarrays
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
// Stores the maximum element
// of the subarray
int mxSubarray = 0;
// Stores the maximum of all
// other elements
int mxOther = 0;
// Find the maximum element
// in the subarray [i, j]
for(int k = i; k <= j; k++)
{
mxSubarray = Math.max(
mxSubarray, arr[k]);
}
// Find the maximum of all
// other elements
for(int k = 0; k < i; k++)
{
mxOther = Math.max(mxOther, arr[k]);
}
for(int k = j + 1; k < n; k++)
{
mxOther = Math.max(mxOther, arr[k]);
}
// If the maximum of subarray
// is greater than twice the
// maximum of other elements
if (mxSubarray > (2 * mxOther))
count++;
}
}
// Print the maximum value obtained
System.out.println(count);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 6, 10, 9, 7, 3 };
int N = arr.length;
countSubarray(arr, N);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to find count of subarrays # which have max element greater than # twice maximum of all other elements def countSubarray(arr, n): # Stores the count of subarrays count = 0 # Generate all possible subarrays for i in range(n): for j in range(i, n, 1): # Stores the maximum element # of the subarray mxSubarray = 0 # Stores the maximum of all # other elements mxOther = 0 # Find the maximum element # in the subarray [i, j] for k in range(i, j + 1, 1): mxSubarray = max(mxSubarray, arr[k]) # Find the maximum of all # other elements for k in range(0, i, 1): mxOther = max(mxOther, arr[k]) for k in range(j + 1,n,1): mxOther = max(mxOther, arr[k]) # If the maximum of subarray # is greater than twice the # maximum of other elements if (mxSubarray > (2 * mxOther)): count += 1 # Print the maximum value obtained print(count) # Driver Code if __name__ == '__main__': arr = [1, 6, 10, 9, 7, 3] N = len(arr) countSubarray(arr, N) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
static void countSubarray(int []arr, int n)
{
// Stores the count of subarrays
int count = 0;
// Generate all possible subarrays
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
// Stores the maximum element
// of the subarray
int mxSubarray = 0;
// Stores the maximum of all
// other elements
int mxOther = 0;
// Find the maximum element
// in the subarray [i, j]
for(int k = i; k <= j; k++)
{
mxSubarray = Math.Max(mxSubarray,
arr[k]);
}
// Find the maximum of all
// other elements
for(int k = 0; k < i; k++)
{
mxOther = Math.Max(mxOther, arr[k]);
}
for(int k = j + 1; k < n; k++)
{
mxOther = Math.Max(mxOther, arr[k]);
}
// If the maximum of subarray
// is greater than twice the
// maximum of other elements
if (mxSubarray > (2 * mxOther))
count++;
}
}
// Print the maximum value obtained
Console.Write(count);
}
// Driver Code
public static void Main()
{
int []arr = { 1, 6, 10, 9, 7, 3 };
int N = arr.Length;
countSubarray(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
function countSubarray(arr, n)
{
// Stores the count of subarrays
let count = 0;
// Generate all possible subarrays
for(let i = 0; i < n; i++)
{
for(let j = i; j < n; j++)
{
// Stores the maximum element
// of the subarray
let mxSubarray = 0;
// Stores the maximum of all
// other elements
let mxOther = 0;
// Find the maximum element
// in the subarray [i, j]
for(let k = i; k <= j; k++)
{
mxSubarray = Math.max(mxSubarray,
arr[k]);
}
// Find the maximum of all
// other elements
for(let k = 0; k < i; k++)
{
mxOther = Math.max(mxOther, arr[k]);
}
for(let k = j + 1; k < n; k++)
{
mxOther = Math.max(
mxOther, arr[k]);
}
// If the maximum of subarray
// is greater than twice the
// maximum of other elements
if (mxSubarray > (2 * mxOther))
count++;
}
}
// Print the maximum value obtained
document.write(count);
}
// Driver Code
let arr = [ 1, 6, 10, 9, 7, 3 ];
let N = arr.length;
countSubarray(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
4
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la observación de que el elemento máximo de la array siempre formará parte del subarreglo y todos los elementos que tengan un valor superior a la mitad del elemento máximo también se incluirán en el subarreglo. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos mx que almacena el elemento máximo de la array .
- Inicialice dos variables L y R para almacenar los extremos izquierdo y derecho del subarreglo.
- Itere sobre el rango [0, N – 1] usando la variable i y si el valor de 2*arr[i] es mayor que mx , entonces inicialice L a i y salga del ciclo .
- Itere sobre el rango [N – 1, 0] de manera inversa usando la variable i y si el valor de 2*arr[i] es mayor que mx , entonces inicialice R a i y salga del bucle .
- Después de completar los pasos anteriores, imprima el valor de (L + 1)*(N – R) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
void countSubarray(int arr[], int n)
{
int count = 0, L = 0, R = 0;
// Stores the maximum element of
// the array
int mx = *max_element(arr, arr + n);
// Traverse the given array
for (int i = 0; i < n; i++) {
// If the value of 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of L
// and break out of loop
L = i;
break;
}
}
for (int i = n - 1; i >= 0; i--) {
// If the value 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of R
// and break out of loop
R = i;
break;
}
}
// Print the final answer
cout << (L + 1) * (n - R);
}
// Driver Code
int main()
{
int arr[] = { 1, 6, 10, 9, 7, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
countSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
static void countSubarray(int[] arr, int n)
{
int L = 0, R = 0;
// Stores the maximum element of
// the array
int mx = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
mx = Math.max(mx, arr[i]);
// Traverse the given array
for (int i = 0; i < n; i++) {
// If the value of 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of L
// and break out of loop
L = i;
break;
}
}
for (int i = n - 1; i >= 0; i--) {
// If the value 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of R
// and break out of loop
R = i;
break;
}
}
// Print the final answer
System.out.println((L + 1) * (n - R));
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 6, 10, 9, 7, 3 };
int N = arr.length;
countSubarray(arr, N);
}
}
// This code is contributed by rishavmahato348.
Python3
# Python3 program for the above approach # Function to find count of subarrays # which have max element greater than # twice maximum of all other elements def countSubarray(arr, n): count = 0 L = 0 R = 0 # Stores the maximum element of # the array mx = max(arr) # Traverse the given array for i in range(n): # If the value of 2*arr[i] is # greater than mx if (arr[i] * 2 > mx): # Update the value of L # and break out of loop L = i break i = n - 1 while (i >= 0): # If the value 2*arr[i] is # greater than mx if (arr[i] * 2 > mx): # Update the value of R # and break out of loop R = i break i -= 1 # Print the final answer print((L + 1) * (n - R)) # Driver Code if __name__ == '__main__': arr = [ 1, 6, 10, 9, 7, 3 ] N = len(arr) countSubarray(arr, N) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG {
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
static void countSubarray(int[] arr, int n)
{
int L = 0, R = 0;
// Stores the maximum element of
// the array
int mx = Int32.MinValue;
for (int i = 0; i < n; i++)
mx = Math.Max(mx, arr[i]);
// Traverse the given array
for (int i = 0; i < n; i++) {
// If the value of 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of L
// and break out of loop
L = i;
break;
}
}
for (int i = n - 1; i >= 0; i--) {
// If the value 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of R
// and break out of loop
R = i;
break;
}
}
// Print the final answer
Console.WriteLine((L + 1) * (n - R));
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 6, 10, 9, 7, 3 };
int N = arr.Length;
countSubarray(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript program for the above approach
// Function to find count of subarrays
// which have max element greater than
// twice maximum of all other elements
function countSubarray(arr, n)
{
var count = 0, L = 0, R = 0;
// Stores the maximum element of
// the array
var mx = Math.max.apply(null, arr);
var i;
// Traverse the given array
for (i = 0; i < n; i++) {
// If the value of 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of L
// and break out of loop
L = i;
break;
}
}
for (i = n - 1; i >= 0; i--) {
// If the value 2*arr[i] is
// greater than mx
if (arr[i] * 2 > mx) {
// Update the value of R
// and break out of loop
R = i;
break;
}
}
// Print the final answer
document.write((L + 1) * (n - R));
}
// Driver Code
var arr = [1, 6, 10, 9, 7, 3]
var N = arr.length;
countSubarray(arr, N);
// This code is contributed by ipg2016107.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)