Dado un arreglo arr , la tarea es encontrar un subarreglo de los elementos del arreglo cuya suma sea estrictamente mayor que el resto de los elementos. El tamaño del subarreglo debe ser mínimo y la suma debe ser máxima y debe estar en orden no creciente.
Ejemplos:
Entrada: arr = [7, 6, 13, 12, 11]
Salida: 13 12
Explicación:
El subarreglo [13, 12] y [13, 11] son mínimos de modo que la suma de sus elementos es estrictamente mayor que el resto de los elementos. Sin embargo, el subarreglo [13, 12] tiene la suma total máxima de sus elementos y, por lo tanto, se devuelve en orden no creciente.
Entrada: arr = [8]
Salida: 8
Acercarse:
- Inicialmente ordenaremos la array arr y definiremos un vector llamado A . Ahora primero calcularemos la suma de toda la array y luego iteramos todo el ciclo desde el lado posterior mientras actualizamos la temperatura consecutivamente. El bucle se ejecuta hasta que la temperatura se vuelve cero.
- En realidad, lo que sucede al iterar el ciclo desde la parte posterior es que cuando iteramos el ciclo desde la parte posterior, estamos considerando los valores máximos. Por lo tanto, podemos decir que podemos alcanzar la condición objetivo en una menor cantidad de tiempo y también tomando menos variables.
- Ahora, a medida que se ejecuta el ciclo, seguimos actualizando el valor de temp simplemente agregando nums[i] y también agregando nums[i] al vector A . Por último, devolvemos el vector A que representa el resultado de salida que queremos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Minimum size Subarray
// with maximum sum in non-increasing order
#include <bits/stdc++.h>
using namespace std;
// Function to find the Minimum size Subarray
void minSet(vector<int>& nums)
{
vector<int> A;
// sort numbers in descending order
sort(nums.begin(), nums.end());
// get total sum of the given array.
int sum = 0;
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
int temp = 0;
// Loop until the sum of numbers
// is greater than sum/2
for (int i = nums.size() - 1;
i >= 0 && temp <= sum / 2;
i--) {
A.push_back(nums[i]);
temp += nums[i];
}
// Print the Minimum size Subarray
for (int i = 0; i < A.size(); i++)
cout << A[i] << " ";
}
// Driver code
int main()
{
vector<int> vec
= { 7, 6, 13, 13, 12, 11 };
minSet(vec);
return 0;
}
Java
// Java program to find the Minimum size Subarray
// with maximum sum in non-increasing order
import java.util.*;
class GFG {
// Function to find the Minimum size Subarray
static void minSet(ArrayList<Integer> nums) {
ArrayList<Integer> A = new ArrayList<Integer> ();
// sort numbers in descending order
Collections.sort(nums);
// get total sum of the given array.
int sum = 0;
for (int i = 0; i<nums.size(); i++)
sum += nums.get(i);
int temp = 0;
// Loop until the sum of numbers
// is greater than sum/2
for (int i = nums.size() - 1;
i >= 0 && temp<= sum / 2;
i--) {
A.add(nums.get(i));
temp += nums.get(i);
}
// Print the Minimum size Subarray
for (int i = 0; i<A.size(); i++)
System.out.print(A.get(i) + " ");
}
// Driver Code
public static void main(String[] args) {
ArrayList<Integer> gfg = new ArrayList<Integer> ();
gfg.add(7);
gfg.add(6);
gfg.add(13);
gfg.add(13);
gfg.add(12);
gfg.add(11);
// Function calling
minSet(gfg);
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to find the Minimum size Subarray # with maximum sum in non-increasing order # Function to find the Minimum size Subarray def minSet(nums) : A = [] # sort numbers in descending order nums.sort() # get total sum of the given array. sum = 0 for i in range(0,len(nums)): sum += nums[i] temp = 0 # Loop until the sum of numbers # is greater than sum/2 for i in range(len(nums)-1, -1, -1): if(temp > sum / 2): break A.append(nums[i]) temp += nums[i] # Print the Minimum size Subarray for i in range(0, len(A)): print(A[i], end = ' ') # Driver code vec = [ 7, 6, 13, 13, 12, 11 ] minSet(vec); # This code is contributed by Sanjit_Prasad
C#
// C# program to find the Minimum size Subarray
// with maximum sum in non-increasing order
using System;
using System.Collections.Generic;
class GFG {
// Function to find the Minimum size Subarray
static void minSet(List<int> nums) {
List<int> A = new List<int> ();
// sort numbers in descending order
nums.Sort();
// get total sum of the given array.
int sum = 0;
for (int i = 0; i < nums.Count; i++)
sum += nums[i];
int temp = 0;
// Loop until the sum of numbers
// is greater than sum/2
for (int i = nums.Count - 1;
i >= 0 && temp<= sum / 2;
i--) {
A.Add(nums[i]);
temp += nums[i];
}
// Print the Minimum size Subarray
for (int i = 0; i<A.Count; i++)
Console.Write(A[i] + " ");
}
// Driver Code
public static void Main(String[] args) {
List<int> gfg = new List<int> ();
gfg.Add(7);
gfg.Add(6);
gfg.Add(13);
gfg.Add(13);
gfg.Add(12);
gfg.Add(11);
// Function calling
minSet(gfg);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the Minimum size Subarray
// with maximum sum in non-increasing order
// Function to find the Minimum size Subarray
function minSet(nums)
{
var A = [];
// sort numbers in descending order
nums.sort((a,b)=>a-b);
// get total sum of the given array.
var sum = 0;
for (var i = 0; i < nums.length; i++)
sum += nums[i];
var temp = 0;
// Loop until the sum of numbers
// is greater than sum/2
for (var i = nums.length - 1;
i >= 0 && temp <= sum / 2;
i--) {
A.push(nums[i]);
temp += nums[i];
}
// Print the Minimum size Subarray
for (var i = 0; i < A.length; i++)
document.write( A[i] + " ");
}
// Driver code
var vec
= [7, 6, 13, 13, 12, 11];
minSet(vec);
</script>
Producción:
13 13 12
Complejidad de tiempo: O(N * log N)
Complejidad de espacio auxiliar: O(N)