Dado un arreglo arr[] que consta de N enteros no negativos, la tarea es encontrar la longitud mínima del subarreglo cuya suma es máxima.
Ejemplo:
Entrada: arr[] = {0, 2, 0, 0, 12, 0, 0, 0}
Salida: 4
Explicación: La suma del subarreglo {2, 0, 0, 12} = 2 + 0 + 0 + 12 = 14, que es la suma máxima posible y la longitud del subarreglo es 4, que es la mínima.Entrada: arr[] = {2, 0, 0}
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles de la array dada e imprimir la longitud de ese subarreglo cuya suma es la suma de la array que tiene la longitud mínima entre todos los subarreglos posibles de la misma suma.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el hecho de que todos los elementos no son negativos, por lo que la suma máxima del subarreglo es la suma del propio arreglo . Por lo tanto, la idea es excluir los ceros finales de cualquiera de los extremos del arreglo para minimizar la longitud del subarreglo resultante con la suma máxima. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos i como 0 y j como (N – 1) que almacenan el índice inicial y final del subarreglo resultante.
- Atraviese la array dada desde el frente hasta que se encuentre un elemento positivo y simultáneamente incremente el valor de i .
- Si el valor de i es N , imprima la longitud máxima del subarreglo resultante como 1 porque contiene todos los elementos como 0 . De lo contrario, recorra la array dada desde el final hasta que se encuentre un elemento positivo y simultáneamente disminuya el valor de j .
- Después de completar los pasos anteriores, imprima el valor de (j – i + 1) como el subarreglo resultante.
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 the minimum length
// of the subarray whose sum is maximum
int minimumSizeSubarray(int arr[],
int N)
{
// Stores the starting and the
// ending index of the resultant
// subarray
int i = 0, j = N - 1;
// Traverse the array until a
// non-zero element is encountered
while (i < N and arr[i] == 0) {
i++;
}
// If the array contains only of 0s
if (i == N)
return 1;
// Traverse the array in reverse until
// a non-zero element is encountered
while (j >= 0 and arr[j] == 0) {
j--;
}
// Return the resultant
// size of the subarray
return (j - i + 1);
}
// Driver Code
int main()
{
int arr[] = { 0, 2, 0, 0, 12,
0, 0, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << minimumSizeSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the minimum length
// of the subarray whose sum is maximum
static int minimumSizeSubarray(int arr[],
int N)
{
// Stores the starting and the
// ending index of the resultant
// subarray
int i = 0, j = N - 1;
// Traverse the array until a
// non-zero element is encountered
while (i < N && arr[i] == 0) {
i++;
}
// If the array contains only of 0s
if (i == N)
return 1;
// Traverse the array in reverse until
// a non-zero element is encountered
while (j >= 0 && arr[j] == 0) {
j--;
}
// Return the resultant
// size of the subarray
return (j - i + 1);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 0, 2, 0, 0, 12,
0, 0, 0 };
int N = arr.length;
System.out.print( minimumSizeSubarray(arr, N));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach # Function to find the minimum length # of the subarray whose sum is maximum def minimumSizeSubarray(arr, N): # Stores the starting and the # ending index of the resultant # subarray i, j = 0, N - 1 # Traverse the array until a # non-zero element is encountered while (i < N and arr[i] == 0): i += 1 # If the array contains only of 0s if (i == N): return 1 # Traverse the array in reverse until # a non-zero element is encountered while (j >= 0 and arr[j] == 0): j -= 1 # Return the resultant # size of the subarray return(j - i + 1) # Driver Code if __name__ == '__main__': arr = [ 0, 2, 0, 0, 12, 0, 0, 0 ] N = len(arr) print(minimumSizeSubarray(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum length
// of the subarray whose sum is maximum
static int minimumSizeSubarray(int[] arr,
int N)
{
// Stores the starting and the
// ending index of the resultant
// subarray
int i = 0, j = N - 1;
// Traverse the array until a
// non-zero element is encountered
while (i < N && arr[i] == 0)
{
i++;
}
// If the array contains only of 0s
if (i == N)
return 1;
// Traverse the array in reverse until
// a non-zero element is encountered
while (j >= 0 && arr[j] == 0)
{
j--;
}
// Return the resultant
// size of the subarray
return (j - i + 1);
}
// Driver code
public static void Main()
{
int[] arr = { 0, 2, 0, 0, 12, 0, 0, 0 };
int N = arr.Length;
Console.Write( minimumSizeSubarray(arr, N));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum length
// of the subarray whose sum is maximum
function minimumSizeSubarray(arr, N)
{
// Stores the starting and the
// ending index of the resultant
// subarray
let i = 0, j = N - 1;
// Traverse the array until a
// non-zero element is encountered
while (i < N && arr[i] == 0) {
i++;
}
// If the array contains only of 0s
if (i == N)
return 1;
// Traverse the array in reverse until
// a non-zero element is encountered
while (j >= 0 && arr[j] == 0) {
j--;
}
// Return the resultant
// size of the subarray
return (j - i + 1);
}
// Driver Code
let arr = [ 0, 2, 0, 0, 12,
0, 0, 0 ];
let N = arr.length;
document.write(minimumSizeSubarray(arr, N));
</script>
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por tmprofessor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA