Dada una array arr[] y un entero M , la tarea es encontrar la longitud de la subsecuencia más larga cuya suma es divisible por M. Si no existe tal subsecuencia, imprima 0 .
Ejemplos:
Entrada: arr[] = {3, 2, 2, 1}, M = 3
Salida: 3
La subsecuencia más larga cuya suma es
divisible por 3 es {3, 2, 1}
Entrada: arr[] = {2, 2 }, M = 3
Salida: 0
Enfoque: una forma sencilla de resolver esto será generar todas las subsucesiones posibles y luego encontrar la más grande entre ellas divisible cuya suma sea divisible por M . Sin embargo, para valores más pequeños de M , se puede utilizar un enfoque basado en programación dinámica .
Veamos primero la relación de recurrencia.
dp[i][curr_mod] = max(dp[i + 1][curr_mod], dp[i + 1][(curr_mod + arr[i]) % m] + 1)
Comprendamos los estados de DP ahora. Aquí, dp[i][curr_mod] almacena la subsecuencia más larga del subarreglo arr[i…N-1] tal que la suma de esta subsecuencia y curr_mod es divisible por M . En cada paso, se puede elegir el índice i actualizando curr_mod o se puede ignorar.
Además, tenga en cuenta que solo es necesario almacenar SUM % m en lugar de la suma completa, ya que esta información es suficiente para completar los estados de DP.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 20
#define maxM 64
// To store the states of DP
int dp[maxN][maxM];
bool v[maxN][maxM];
// Function to return the length
// of the longest subsequence
// whose sum is divisible by m
int findLen(int* arr, int i, int curr,
int n, int m)
{
// Base case
if (i == n) {
if (!curr)
return 0;
else
return -1;
}
// If the state has been solved before
// return the value of the state
if (v[i][curr])
return dp[i][curr];
// Setting the state as solved
v[i][curr] = 1;
// Recurrence relation
int l = findLen(arr, i + 1, curr, n, m);
int r = findLen(arr, i + 1,
(curr + arr[i]) % m, n, m);
dp[i][curr] = l;
if (r != -1)
dp[i][curr] = max(dp[i][curr], r + 1);
return dp[i][curr];
}
// Driver code
int main()
{
int arr[] = { 3, 2, 2, 1 };
int n = sizeof(arr) / sizeof(int);
int m = 3;
cout << findLen(arr, 0, 0, n, m);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int maxN = 20;
static int maxM = 64;
// To store the states of DP
static int [][]dp = new int[maxN][maxM];
static boolean [][]v = new boolean[maxN][maxM];
// Function to return the length
// of the longest subsequence
// whose sum is divisible by m
static int findLen(int[] arr, int i,
int curr, int n, int m)
{
// Base case
if (i == n)
{
if (curr == 0)
return 0;
else
return -1;
}
// If the state has been solved before
// return the value of the state
if (v[i][curr])
return dp[i][curr];
// Setting the state as solved
v[i][curr] = true;
// Recurrence relation
int l = findLen(arr, i + 1, curr, n, m);
int r = findLen(arr, i + 1,
(curr + arr[i]) % m, n, m);
dp[i][curr] = l;
if (r != -1)
dp[i][curr] = Math.max(dp[i][curr], r + 1);
return dp[i][curr];
}
// Driver code
public static void main(String []args)
{
int arr[] = { 3, 2, 2, 1 };
int n = arr.length;
int m = 3;
System.out.println(findLen(arr, 0, 0, n, m));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach import numpy as np maxN = 20 maxM = 64 # To store the states of DP dp = np.zeros((maxN, maxM)); v = np.zeros((maxN, maxM)); # Function to return the length # of the longest subsequence # whose sum is divisible by m def findLen(arr, i, curr, n, m) : # Base case if (i == n) : if (not curr) : return 0; else : return -1; # If the state has been solved before # return the value of the state if (v[i][curr]) : return dp[i][curr]; # Setting the state as solved v[i][curr] = 1; # Recurrence relation l = findLen(arr, i + 1, curr, n, m); r = findLen(arr, i + 1, (curr + arr[i]) % m, n, m); dp[i][curr] = l; if (r != -1) : dp[i][curr] = max(dp[i][curr], r + 1); return dp[i][curr]; # Driver code if __name__ == "__main__" : arr = [ 3, 2, 2, 1 ]; n = len(arr); m = 3; print(findLen(arr, 0, 0, n, m)); # This code is contributed by AnkitRai
C#
// C# implementation of the approach
using System;
class GFG
{
static int maxN = 20;
static int maxM = 64;
// To store the states of DP
static int [,]dp = new int[maxN, maxM];
static Boolean [,]v = new Boolean[maxN, maxM];
// Function to return the length
// of the longest subsequence
// whose sum is divisible by m
static int findLen(int[] arr, int i,
int curr, int n, int m)
{
// Base case
if (i == n)
{
if (curr == 0)
return 0;
else
return -1;
}
// If the state has been solved before
// return the value of the state
if (v[i, curr])
return dp[i, curr];
// Setting the state as solved
v[i, curr] = true;
// Recurrence relation
int l = findLen(arr, i + 1, curr, n, m);
int r = findLen(arr, i + 1,
(curr + arr[i]) % m, n, m);
dp[i, curr] = l;
if (r != -1)
dp[i, curr] = Math.Max(dp[i, curr], r + 1);
return dp[i, curr];
}
// Driver code
public static void Main(String []args)
{
int []arr = { 3, 2, 2, 1 };
int n = arr.Length;
int m = 3;
Console.WriteLine(findLen(arr, 0, 0, n, m));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
var maxN = 20
var maxM = 64
// To store the states of DP
var dp = Array.from(Array(maxN), ()=> Array(maxM).fill(0));
var v = Array.from(Array(maxN), ()=> Array(maxM).fill(false));
// Function to return the length
// of the longest subsequence
// whose sum is divisible by m
function findLen(arr, i, curr, n, m)
{
// Base case
if (i == n) {
if (!curr)
return 0;
else
return -1;
}
// If the state has been solved before
// return the value of the state
if (v[i][curr])
return dp[i][curr];
// Setting the state as solved
v[i][curr] = 1;
// Recurrence relation
var l = findLen(arr, i + 1, curr, n, m);
var r = findLen(arr, i + 1, (curr + arr[i]) % m, n, m);
dp[i][curr] = l;
if (r != -1)
dp[i][curr] = Math.max(dp[i][curr], r + 1);
return dp[i][curr];
}
// Driver code
var arr = [3, 2, 2, 1];
var n = arr.length;
var m = 3;
document.write( findLen(arr, 0, 0, n, m));
</script>
3
Complejidad Temporal: O(N * M)
Espacio Auxiliar : O(N * M).
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA