Самая длинная подпоследовательность, сумма которой делится на заданное число
Для массива arr [] и целого числа M задача состоит в том, чтобы найти длину самой длинной подпоследовательности, сумма которой делится на M. Если такой подпоследовательности нет, выведите 0 .
Примеры:
Input: arr[] = {3, 2, 2, 1}, M = 3
Output: 3
Longest sub-sequence whose sum is
divisible by 3 is {3, 2, 1}
Input: arr[] = {2, 2}, M = 3
Output: 0
Подход: простой способ решить эту проблему - сгенерировать все возможные подпоследовательности, а затем найти среди них наибольшую делимую, сумма которой делится на M. Однако для меньших значений M можно использовать подход, основанный на динамическом программировании.
Давайте сначала посмотрим на рекуррентное отношение.
dp[i][curr_mod] = max(dp[i + 1][curr_mod], dp[i + 1][(curr_mod + arr[i]) % m] + 1)
Let’s understand the states of DP now. Here, dp[i][curr_mod] stores the longest subsequence of subarray arr[i…N-1] such that the sum of this subsequence and curr_mod is divisible by M. At each step, either index i can be chosen updating curr_mod or it can be ignored.
Also, note that only SUM % m needs to be stored instead of the entire sum as this information is sufficient to complete the states of DP.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define maxN 20#define maxM 64// To store the states of DPint dp[maxN][maxM];bool v[maxN][maxM];// Function to return the length// of the longest subsequence// whose sum is divisible by mint 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 codeint 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 approachclass GFG{static int maxN = 20;static int maxM = 64;// To store the states of DPstatic 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 mstatic 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 codepublic 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 approachimport numpy as npmaxN = 20maxM = 64# To store the states of DPdp = np.zeros((maxN, maxM));v = np.zeros((maxN, maxM));# Function to return the length# of the longest subsequence# whose sum is divisible by mdef 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 codeif __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 approachusing System; class GFG{ static int maxN = 20;static int maxM = 64;// To store the states of DPstatic 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 mstatic 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 codepublic 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 approachvar maxN = 20var maxM = 64// To store the states of DPvar 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 mfunction 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 codevar arr = [3, 2, 2, 1];var n = arr.length;var m = 3;document.write( findLen(arr, 0, 0, n, m));</script> |
3
Сложность времени: O (N * M)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.