Dada una array arr[] que consta de N enteros, la tarea es encontrar el tamaño del subconjunto más grande de la array de modo que se pueda formar un triángulo a partir de cualquiera de los tres enteros del subconjunto como los lados de un triángulo.
Ejemplos:
Entrada: arr[] = {1, 4, 7, 4}
Salida: 3
Explicación: Los subconjuntos posibles que siguen las condiciones dadas son {1, 4, 4} y {4, 4, 7}. El tamaño de ambos subconjuntos es 3, que es el máximo posible.Entrada: arr[] = {2, 7, 4, 1, 6, 9, 5, 3}
Salida: 4
Enfoque: el problema dado se puede resolver con la ayuda del enfoque codicioso utilizando la técnica de la ventana deslizante . Se sabe que para un triángulo cuyos lados tienen longitudes A , B y C , A + B > C debe cumplirse donde A y B son los lados con longitudes más pequeñas. Con base en la observación anterior, el problema dado se puede resolver siguiendo los siguientes pasos:
- Ordene la array dada arr[] en orden no decreciente .
- Mantenga dos variables i y j donde yo hago un seguimiento del punto de inicio de la ventana actual y j hago un seguimiento del punto final de la ventana actual. Inicialmente i = 0 y j = i + 2 .
- Incremente el valor de j hasta arr[i] + arr[i+1] > arr[j] y realice un seguimiento del valor máximo de j – i en una variable maxSize . Si arr[i] + arr[i+1] > arr[j] , incrementa el valor de i en 1 .
- Siga el paso anterior hasta que se haya recorrido toda la array.
- Después de completar los pasos anteriores, el valor almacenado en maxSize es el resultado requerido.
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 maximum size of
// the subset of the given array such
// that a triangle can be formed from any
// three integers of the subset as sides
int maximizeSubset(int arr[], int N)
{
// Sort arr[] in increasing order
sort(arr, arr + N);
// Stores the maximum size of a valid
// subset of the given array
int maxSize = 0;
// Stores the starting index of the
// current window
int i = 0;
// Stores the last index of the
// current window
int j = i + 2;
// Iterate over the array arr[]
while (i < N - 2) {
// Increment j till the value
// of arr[i] + arr[i + 1] >
// arr[j] holds true
while (arr[i] + arr[i + 1] > arr[j]) {
j++;
}
// Update the value of maxSize
maxSize = max(maxSize, j - i);
i++;
j = max(j, i + 2);
}
// Return Answer
return maxSize;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 4, 1, 6, 9, 5, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximizeSubset(arr, N) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum size of
// the subset of the given array such
// that a triangle can be formed from any
// three integers of the subset as sides
static int maximizeSubset(int arr[], int N)
{
// Sort arr[] in increasing order
Arrays.sort(arr);
// Stores the maximum size of a valid
// subset of the given array
int maxSize = 0;
// Stores the starting index of the
// current window
int i = 0;
// Stores the last index of the
// current window
int j = i + 2;
// Iterate over the array arr[]
while (i < N - 2) {
// Increment j till the value
// of arr[i] + arr[i + 1] >
// arr[j] holds true
while (j<N && arr[i] + arr[i + 1] > arr[j]) {
j++;
}
// Update the value of maxSize
maxSize = Math.max(maxSize, j - i);
i++;
j = Math.max(j, i + 2);
}
// Return Answer
return maxSize;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 7, 4, 1, 6, 9, 5, 3 };
int N = arr.length;
System.out.print(maximizeSubset(arr, N) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# python program for the above approach # Function to find the maximum size of # the subset of the given array such # that a triangle can be formed from any # three integers of the subset as sides def maximizeSubset(arr, N): # Sort arr[] in increasing order arr.sort() # Stores the maximum size of a valid # subset of the given array maxSize = 0 # Stores the starting index of the # current window i = 0 # Stores the last index of the # current window j = i + 2 # Iterate over the array arr[] while (i < N - 2): # Increment j till the value # of arr[i] + arr[i + 1] > # arr[j] holds true while (j < N and arr[i] + arr[i + 1] > arr[j]): j = j + 1 # Update the value of maxSize maxSize = max(maxSize, j - i) i += 1 j = max(j, i + 2) # Return Answer return maxSize # Driver Code if __name__ == "__main__": arr = [2, 7, 4, 1, 6, 9, 5, 3] N = len(arr) print(maximizeSubset(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum size of
// the subset of the given array such
// that a triangle can be formed from any
// three integers of the subset as sides
static int maximizeSubset(int []arr, int N)
{
// Sort arr[] in increasing order
Array.Sort(arr);
// Stores the maximum size of a valid
// subset of the given array
int maxSize = 0;
// Stores the starting index of the
// current window
int i = 0;
// Stores the last index of the
// current window
int j = i + 2;
// Iterate over the array arr[]
while (i < N - 2) {
// Increment j till the value
// of arr[i] + arr[i + 1] >
// arr[j] holds true
if(j>=N || i+1 >=N)
break;
while (j<N && arr[i] + arr[i + 1] > arr[j]) {
j++;
}
// Update the value of maxSize
maxSize = Math.Max(maxSize, j - i);
i++;
j = Math.Max(j, i + 2);
}
// Return Answer
return maxSize;
}
// Driver Code
public static void Main()
{
int []arr = { 2, 7, 4, 1, 6, 9, 5, 3 };
int N = arr.Length;
Console.Write(maximizeSubset(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum size of
// the subset of the given array such
// that a triangle can be formed from any
// three integers of the subset as sides
const maximizeSubset = (arr, N) => {
// Sort arr[] in increasing order
arr.sort((a, b) => a - b)
// Stores the maximum size of a valid
// subset of the given array
let maxSize = 0;
// Stores the starting index of the
// current window
let i = 0;
// Stores the last index of the
// current window
let j = i + 2;
// Iterate over the array arr[]
while (i < N - 2) {
// Increment j till the value
// of arr[i] + arr[i + 1] >
// arr[j] holds true
while (arr[i] + arr[i + 1] > arr[j]) {
j++;
}
// Update the value of maxSize
maxSize = Math.max(maxSize, j - i);
i++;
j = Math.max(j, i + 2);
}
// Return Answer
return maxSize;
}
// Driver Code
let arr = [2, 7, 4, 1, 6, 9, 5, 3];
let N = arr.length;
document.write(maximizeSubset(arr, N));
// This code is contributed by rakeshsahni
</script>
Producción:
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)