Longitud máxima de string después de elegir strings de una array dada con condiciones dadas

Dada una array de strings S[] de tamaño N , la tarea es encontrar el tamaño máximo de la string resultante formada agregando algunas strings y siguiendo la condición dada de que si se elige una string de tamaño K para agregar la string resultante, entonces las siguientes strings K/2 no se pueden seleccionar para que formen parte de la array resultante.

 Ejemplos:

Entrada: S[] = {“bien”, “hacer”, “hola”, “por”}
Salida: 6
Explicación: Elija “bien” y omita “hacer” y “hola”(tamaño(“bien”)/2 ) y luego seleccione “por”. Entonces, el tamaño será 6.

Entrada: s[] = {“geeks”, “para”, “geeks”, “es”, “mejor”}
Salida: 9

Enfoque: Este problema se puede resolver usando memoization . Siga los pasos a continuación:

• Para cada string S[i] , hay dos opciones, es decir, elegir la string actual o no.
• Entonces, si se elige la string, su longitud, digamos K , contribuirá a la longitud de la array resultante y ahora, solo se pueden elegir las strings después de K/2 .
• Ahora, si la string está excluida, simplemente muévase más.
• Escriba la respuesta de acuerdo con la observación anterior

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the
// maximum length of the resultant string
int maxsum(string S[], int N, int i,
           vector<int>& dp)
{
    // If index gets out of bound return 0
    if (i >= N)
        return 0;
 
    // If value not already computed
    // then compute it
    if (dp[i] == -1) {
 
        // To include the current string
        int op1
            = S[i].size()
              + maxsum(S, N,
                       (i + S[i].size() / 2)
                           + 1,
                       dp);
 
        // To exclude the current string
        int op2 = maxsum(S, N, i + 1, dp);
 
        // Maximum of both the options
        dp[i] = max(op1, op2);
    }
    return dp[i];
}
 
// Driver Code
int main()
{
    string S[] = { "geeks", "for", "geeks",
                   "is", "best" };
    int N = sizeof(S) / sizeof(S[0]);
    vector<int> dp(N, -1);
    cout << maxsum(S, N, 0, dp);
    return 0;
}

// Java implementation of the above approach
import java.util.Arrays;
 
class GFG {
 
  // Recursive function to find the
  // maximum length of the resultant string
  static int maxsum(String S[], int N, int i, int[] dp)
  {
 
    // If index gets out of bound return 0
    if (i >= N)
      return 0;
 
    // If value not already computed
    // then compute it
    if (dp[i] == -1) {
 
      // To include the current string
      int op1 = S[i].length()
        + maxsum(S, N,
                 (i + S[i].length() / 2)
                 + 1,
                 dp);
 
      // To exclude the current string
      int op2 = maxsum(S, N, i + 1, dp);
 
      // Maximum of both the options
      dp[i] = Math.max(op1, op2);
    }
    return dp[i];
  }
 
  // Driver Code
  public static void main(String args[]) {
    String S[] = { "geeks", "for", "geeks", "is", "best" };
    int N = S.length;
    int[] dp = new int[N];
    Arrays.fill(dp, -1);
    System.out.println(maxsum(S, N, 0, dp));
  }
}
 
// This code is contributed by saurabh_jaiswal.

# Python implementation of the above approach
 
# Recursive function to find the
# maximum length of the resultant string
def maxsum(S, N, i, dp):
 
    # If index gets out of bound return 0
    if (i >= N):
        return 0
 
    # If value not already computed
    # then compute it
    if (dp[i] == -1):
 
        # To include the current string
        op1 = int(len(S[i]) + maxsum(S, N, (i + len(S[i]) // 2)+1, dp))
 
        # To exclude the current string
        op2 = int(maxsum(S, N, i + 1, dp))
 
        # Maximum of both the options
        dp[i] = max(op1, op2)
 
    return dp[i]
 
# Driver Code
S = ["geeks", "for", "geeks", "is", "best"]
N = len(S)
dp = []
for i in range(0, N):
    dp.append(-1)
 
print(maxsum(S, N, 0, dp))
 
# This code is contributed by Taranpreet

// C# implementation of the above approach
using System;
public class GFG
{
 
  // Recursive function to find the
  // maximum length of the resultant string
  static int maxsum(String []S, int N, int i, int[] dp)
  {
 
    // If index gets out of bound return 0
    if (i >= N)
      return 0;
 
    // If value not already computed
    // then compute it
    if (dp[i] == -1) {
 
      // To include the current string
      int op1 = S[i].Length + maxsum(S, N, (i + S[i].Length / 2) + 1, dp);
 
      // To exclude the current string
      int op2 = maxsum(S, N, i + 1, dp);
 
      // Maximum of both the options
      dp[i] = Math.Max(op1, op2);
    }
    return dp[i];
  }
 
  // Driver Code
  public static void Main(String []args)
  {
    String []S = { "geeks", "for", "geeks", "is", "best" };
    int N = S.Length;
    int[] dp = new int[N];
    for(int i = 0;i<N;i++)
      dp[i] = -1;
    Console.WriteLine(maxsum(S, N, 0, dp));
  }
}
 
// This code is contributed by umadevi9616

<script>
       // JavaScript code for the above approach
 
       // Recursive function to find the
       // maximum length of the resultant string
       function maxsum(S, N, i,
           dp) {
           // If index gets out of bound return 0
           if (i >= N)
               return 0;
 
           // If value not already computed
           // then compute it
           if (dp[i] == -1) {
 
               // To include the current string
               let op1
                   = S[i].length
                   + maxsum(S, N,
                       (i + Math.floor(S[i].length / 2))
                       + 1,
                       dp);
 
               // To exclude the current string
               let op2 = maxsum(S, N, i + 1, dp);
 
               // Maximum of both the options
               dp[i] = Math.max(op1, op2);
           }
           return dp[i];
       }
 
       // Driver Code
 
       let S = ["geeks", "for", "geeks",
           "is", "best"];
       let N = S.length;
       let dp = new Array(N).fill(-1)
       document.write(maxsum(S, N, 0, dp));
 
      // This code is contributed by Potta Lokesh
   </script>

9

Complejidad temporal: O(N)
Espacio auxiliar: O(N)