Длина самой длинной общей подпоследовательности с заданной суммой K

Даны два массива a[] и b[] и целое число K , задача состоит в том, чтобы найти длину самой длинной общей подпоследовательности, сумма элементов которой равна K .

Примеры:

Input: a[] = { 9, 11, 2, 1, 6, 2, 7}, b[] = {1, 2, 6, 9, 2, 3, 11, 7}, K = 18
Output: 3
Explanation: Subsequence { 11, 7 }  and { 9, 2, 7 } has sum equal to 18. 
Among them { 9, 2, 7 } is longest. Therefore the output will be 3.

Input: a[] = { 2, 5, 2, 5, 7, 9, 4, 2}, b[] = { 1, 6, 2, 7, 8 }, K = 8
Output: -1

Подход: подход к решению основан на концепции самой длинной общей подпоследовательности, и нам нужно проверить, равна ли сумма элементов подпоследовательности заданному значению. Выполните шаги, указанные ниже;

• Рассмотрим переменную sum , инициализированную заданным значением.
• Каждый раз, когда элементы входят в подпоследовательность, уменьшать значение суммы на этот элемент.
• В базовом условии проверьте, равно ли значение суммы 0, что означает, что эта подпоследовательность имеет сумму, равную K . Поэтому возвращайте 0, когда сумма равна нулю, иначе возвращайте INT_MIN.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (2 ^N ), максимальный размер N среди обоих массивов
Вспомогательное пространство: O(1)

Эффективный подход. Эффективный подход заключается в использовании мемоизации для уменьшения временной сложности, когда каждое состояние хранит максимальную длину подпоследовательности, имеющей сумму. Используйте карту , чтобы добиться этого.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N*M)
Вспомогательное пространство: O(N * M)