Suma máxima de subsecuencias de una array dada que es un cuadrado perfecto

Dada una array arr[] , la tarea es encontrar la suma de una subsecuencia que forme un cuadrado perfecto . Si hay múltiples subsecuencias que tienen una suma igual a un cuadrado perfecto, imprime la suma máxima .
Explicación: 
 

Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9} 
Salida: 36 
Explicación: 
La suma máxima posible que es un cuadrado perfecto que se puede obtener de la array es 36 obtenida de la subsecuencia {1, 5, 6, 7, 8, 9}.
Entrada: arr[] = {9, 10} 
Salida: 9 
 

Enfoque ingenuo: genere todas las subsecuencias posibles de una array dada y, para cada subsecuencia, verifique si su suma es un cuadrado perfecto . Si se encuentra tal suma, actualice la suma máxima . Finalmente, imprima la suma máxima obtenida. 
Complejidad de Tiempo: O(N * 2 ^N ) 
Espacio Auxiliar: O(N)
 

Enfoque eficiente: 
el enfoque anterior se puede optimizar utilizando el enfoque de programación dinámica . 
Siga los pasos que se indican a continuación: 
 

• Calcular la suma de la array.
• Iterar k en el rango [√sum, 0] y verificar si existe alguna subsecuencia con esa suma k ² . Para cada k , siga los pasos a continuación: 
  • Inicializa el subconjunto de array booleana[][] de dimensiones N * sum , donde sum denota el valor actual de k ² .
  • subconjunto[i][j] indica si existe o no una subsecuencia de tamaño i con suma j .
  • Inicialice la primera columna y la primera fila como verdadero y falso respectivamente de subconjunto[][] .
  • Ejecute dos bucles anidados, el exterior desde i en el rango [1, N] y el interior j en el rango [1, suma] para llenar la array del subconjunto [][] de forma ascendente según las siguientes condiciones: 
    • si (j < arr[i – 1]), entonces subconjunto[i][j] = subconjunto[i – 1][j]
    • si (j >= arr[i – 1]), entonces subconjunto[i][j] = subconjunto[i – 1][j] || subconjunto[i – 1][j – arr[i – 1]]
  • Finalmente, devuelve el subconjunto[n][suma] .
• El primer k para el cual el subconjunto[n][k] es verdadero, da la máxima suma de subsecuencias posible requerida k ² .

A continuación se muestra la implementación del enfoque anterior:
 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum)
{
    bool subset[n + 1][sum + 1];
 
    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
        subset[i][0] = true;
 
    // If sum is not 0 and arr[] is empty,
    // then answer is false
    for (int i = 1; i <= sum; i++)
        subset[0][i] = false;
 
    // Fill the subset table in bottom up manner
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
 
            if (j < arr[i - 1])
                subset[i][j] = subset[i - 1][j];
 
            if (j >= arr[i - 1])
                subset[i][j]
                    = subset[i - 1][j]
                      || subset[i - 1][j - arr[i - 1]];
        }
    }
 
    return subset[n][sum];
}
// Function to find the sum
int findSum(int* arr, int n)
{
    int sum = 0;
    // Find sum of all values
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
 
    int val = sqrt(sum);
 
    for (int i = val; i >= 0; i--) {
        if (isSubsetSum(arr, n, i * i)) {
            // return the value;
            return i * i;
        }
    }
 
    return 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSum(arr, n) << endl;
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
static boolean isSubsetSum(int arr[],
                           int n, int sum)
{
    boolean[][] subset = new boolean[n + 1][sum + 1];
 
    // If sum is 0, then answer is true
    for(int i = 0; i <= n; i++)
        subset[i][0] = true;
 
    // If sum is not 0 and arr[] is empty,
    // then answer is false
    for(int i = 1; i <= sum; i++)
        subset[0][i] = false;
 
    // Fill the subset table in bottom up manner
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= sum; j++)
        {
            if (j < arr[i - 1])
                subset[i][j] = subset[i - 1][j];
 
            if (j >= arr[i - 1])
                subset[i][j] = subset[i - 1][j] ||
                subset[i - 1][j - arr[i - 1]];
        }
    }
    return subset[n][sum];
}
 
// Function to find the sum
static int findSum(int[] arr, int n)
{
    int sum = 0;
     
    // Find sum of all values
    for(int i = 0; i < n; i++)
    {
        sum += arr[i];
    }
 
    int val = (int)Math.sqrt(sum);
 
    for(int i = val; i >= 0; i--)
    {
        if (isSubsetSum(arr, n, i * i))
        {
             
            // return the value;
            return i * i;
        }
    }
    return 0;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int n = arr.length;
     
    System.out.println(findSum(arr, n));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement
# the above approach
import math
 
def isSubsetSum(arr, n, sum):
     
    subset = [ [ True for x in range(sum + 1) ]
                      for y in range(n + 1) ]
 
    # If sum is 0, then answer is true
    for i in range(n + 1):
        subset[i][0] = True
 
    # If sum is not 0 and arr[] is empty,
    # then answer is false
    for i in range(1, sum + 1):
        subset[0][i] = False
 
    # Fill the subset table in bottom up manner
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
 
            if (j < arr[i - 1]):
                subset[i][j] = subset[i - 1][j]
 
            if (j >= arr[i - 1]):
                subset[i][j] = (subset[i - 1][j] or
                                subset[i - 1][j -
                                   arr[i - 1]])
                                    
    return subset[n][sum]
 
# Function to find the sum
def findSum(arr, n):
     
    sum = 0
     
    # Find sum of all values
    for i in range(n):
        sum += arr[i]
 
    val = int(math.sqrt(sum))
 
    for i in range(val, -1, -1):
        if (isSubsetSum(arr, n, i * i)):
             
            # Return the value;
            return i * i
             
    return 0
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9]
    n = len(arr)
     
    print(findSum(arr, n))
 
# This code is contributed by chitranayal

// C# program to implement
// the above approach
using System;
 
class GFG{
 
static bool isSubsetSum(int []arr,
                        int n, int sum)
{
    bool[,] subset = new bool[n + 1, sum + 1];
 
    // If sum is 0, then answer is true
    for(int i = 0; i <= n; i++)
        subset[i, 0] = true;
 
    // If sum is not 0 and []arr is empty,
    // then answer is false
    for(int i = 1; i <= sum; i++)
        subset[0, i] = false;
 
    // Fill the subset table in bottom up manner
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= sum; j++)
        {
            if (j < arr[i - 1])
                subset[i, j] = subset[i - 1, j];
 
            if (j >= arr[i - 1])
                subset[i, j] = subset[i - 1, j] ||
                subset[i - 1, j - arr[i - 1]];
        }
    }
    return subset[n, sum];
}
 
// Function to find the sum
static int findSum(int[] arr, int n)
{
    int sum = 0;
     
    // Find sum of all values
    for(int i = 0; i < n; i++)
    {
        sum += arr[i];
    }
 
    int val = (int)Math.Sqrt(sum);
 
    for(int i = val; i >= 0; i--)
    {
        if (isSubsetSum(arr, n, i * i))
        {
             
            // return the value;
            return i * i;
        }
    }
    return 0;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int n = arr.Length;
     
    Console.WriteLine(findSum(arr, n));
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
// JavaScript program to implement
// the above approach
 
function isSubsetSum(arr, n, sum)
{
    let subset = new Array(n + 1);
    for (var i = 0; i < subset.length; i++) {
    subset[i] = new Array(2);
    }
   
    // If sum is 0, then answer is true
    for(let i = 0; i <= n; i++)
        subset[i][0] = true;
   
    // If sum is not 0 and arr[] is empty,
    // then answer is false
    for(let i = 1; i <= sum; i++)
        subset[0][i] = false;
   
    // Fill the subset table in bottom up manner
    for(let i = 1; i <= n; i++)
    {
        for(let j = 1; j <= sum; j++)
        {
            if (j < arr[i - 1])
                subset[i][j] = subset[i - 1][j];
   
            if (j >= arr[i - 1])
                subset[i][j] = subset[i - 1][j] ||
                subset[i - 1][j - arr[i - 1]];
        }
    }
    return subset[n][sum];
}
   
// Function to find the sum
function findSum(arr, n)
{
    let sum = 0;
       
    // Find sum of all values
    for(let i = 0; i < n; i++)
    {
        sum += arr[i];
    }
   
    let val = Math.floor(Math.sqrt(sum));
   
    for(let i = val; i >= 0; i--)
    {
        if (isSubsetSum(arr, n, i * i))
        {
               
            // return the value;
            return i * i;
        }
    }
    return 0;
}
 
    // Driver Code
         
    let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
    let n = arr.length;
       
    document.write(findSum(arr, n));
 
</script>

36

Complejidad de Tiempo: O(N * SUM)  
Espacio Auxiliar: O(N * SUM)