Dada una array de enteros arr[] , la tarea es dividir esta array en dos subconjuntos no vacíos de modo que la suma del cuadrado de la suma de ambos subconjuntos sea máxima y los tamaños de ambos subconjuntos no deben diferir en más de 1 Ejemplos :
Entrada: arr[] = {1, 2, 3}
Salida: 26
Explicación:
La suma de los pares de subconjuntos es la siguiente
(1) 2 + (2 + 3) 2 = 26
(2) 2 + (1 + 3) 2 = 20
(3) 2 + (1 + 2) 2 = 18
El máximo entre estos es 26, por lo que la suma requerida es 26
Entrada: arr[] = {7, 2, 13, 4, 25, 8}
Salida: 2845
Enfoque: La tarea es maximizar la suma de a 2 + b 2 donde a y b son la suma de los dos subconjuntos y a + b = C (constante), es decir, la suma de todo el arreglo. La suma máxima se puede lograr ordenando la array y dividiendo los primeros N/2 – 1 elementos más pequeños en un subconjunto y el resto N/2 + 1 elementos en el otro subconjunto. De esta manera, la suma se puede maximizar manteniendo la diferencia de tamaño en 1 como máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum of the
// square of the sum of two subsets of an array
int maxSquareSubsetSum(int* A, int N)
{
// Initialize variables to store
// the sum of subsets
int sub1 = 0, sub2 = 0;
// Sorting the array
sort(A, A + N);
// Loop through the array
for (int i = 0; i < N; i++) {
// Sum of the first subset
if (i < (N / 2) - 1)
sub1 += A[i];
// Sum of the second subset
else
sub2 += A[i];
}
// Return the maximum sum of
// the square of the sum of subsets
return sub1 * sub1 + sub2 * sub2;
}
// Driver code
int main()
{
int arr[] = { 7, 2, 13, 4, 25, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxSquareSubsetSum(arr, N);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the maximum sum of the
// square of the sum of two subsets of an array
static int maxSquareSubsetSum(int []A, int N)
{
// Initialize variables to store
// the sum of subsets
int sub1 = 0, sub2 = 0;
// Sorting the array
Arrays.sort(A);
// Loop through the array
for (int i = 0; i < N; i++)
{
// Sum of the first subset
if (i < (N / 2) - 1)
sub1 += A[i];
// Sum of the second subset
else
sub2 += A[i];
}
// Return the maximum sum of
// the square of the sum of subsets
return sub1 * sub1 + sub2 * sub2;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 7, 2, 13, 4, 25, 8 };
int N = arr.length;
System.out.println(maxSquareSubsetSum(arr, N));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the maximum sum of the # square of the sum of two subsets of an array def maxSquareSubsetSum(A, N) : # Initialize variables to store # the sum of subsets sub1 = 0; sub2 = 0; # Sorting the array A.sort(); # Loop through the array for i in range(N) : # Sum of the first subset if (i < (N // 2) - 1) : sub1 += A[i]; # Sum of the second subset else : sub2 += A[i]; # Return the maximum sum of # the square of the sum of subsets return sub1 * sub1 + sub2 * sub2; # Driver code if __name__ == "__main__" : arr = [ 7, 2, 13, 4, 25, 8 ]; N = len(arr); print(maxSquareSubsetSum(arr, N)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the maximum sum of the
// square of the sum of two subsets of an array
static int maxSquareSubsetSum(int []A, int N)
{
// Initialize variables to store
// the sum of subsets
int sub1 = 0, sub2 = 0;
// Sorting the array
Array.Sort(A);
// Loop through the array
for (int i = 0; i < N; i++)
{
// Sum of the first subset
if (i < (N / 2) - 1)
sub1 += A[i];
// Sum of the second subset
else
sub2 += A[i];
}
// Return the maximum sum of
// the square of the sum of subsets
return sub1 * sub1 + sub2 * sub2;
}
// Driver code
public static void Main()
{
int []arr = { 7, 2, 13, 4, 25, 8 };
int N = arr.Length;
Console.WriteLine(maxSquareSubsetSum(arr, N));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Creating the bblSort function
function bblSort(arr){
for(var i = 0; i < arr.length; i++){
// Last i elements are already in place
for(var j = 0; j < ( arr.length - i -1 ); j++){
// Checking if the item at present iteration
// is greater than the next iteration
if(arr[j] > arr[j+1]){
// If the condition is true then swap them
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j+1] = temp
}
}
}
// return the sorted array
return arr;
}
// Function to return the maximum sum of the
// square of the sum of two subsets of an array
function maxSquareSubsetSum(A , N) {
// Initialize variables to store
// the sum of subsets
var sub1 = 0, sub2 = 0;
// Sorting the array
A = bblSort(A);
// Loop through the array
for (i = 0; i < N; i++) {
// Sum of the first subset
if (i < (N / 2) - 1)
sub1 += A[i];
// Sum of the second subset
else
sub2 += A[i];
}
// Return the maximum sum of
// the square of the sum of subsets
return sub1 * sub1 + sub2 * sub2;
}
// Driver code
var arr = [ 7, 2, 13, 4, 25, 8 ];
var N = arr.length;
document.write(maxSquareSubsetSum(arr, N));
// This code is contributed by todaysgaurav
</script>
2845
Complejidad del tiempo: O(N*log(N))
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA