Максимальное количество чисел, которые можно удалить с конца любого массива с общей суммой не более K

Даны два массива S1 и S2 , содержащие N и M целых чисел, и целое число K , задача состоит в том, чтобы найти максимальное количество целых чисел, которые можно удалить с конца любого заданного массива так, чтобы сумма удаленных элементов была меньше или равна к К .

Пример:

Input: S1[] = {1, 2, 3}, S2[] = {1, 2, 4}, K = 10
Output: 5
Explanation: All the elements of S1 i.e, {1, 2, 3} and two elements of S2 i.e, {1, 2} can be removed from the given arrays as their sum is 9 which is less than 10. Hence, the number of integers that can be removes is 5 which is the maximum possible.

Input: S1[] = {12, 21, 102}, S2[] = {167, 244, 377, 56, 235, 269, 23}, K = 1000
Output: 7

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

• Во-первых, проверьте, сколько чисел S1 можно получить, учитывая, что S2 не существует.
• Теперь текущий ответ, полученный на шаге 1, сохраняется как окончательный ответ.
• Теперь начните обход S2 и продолжайте вставлять элементы в набор удаленных целых чисел. Если сумма удаленных элементов превышает K в любой точке, удаляйте целые числа S1 , которые включены из последнего, пока сумма не станет меньше или равна K .
• Обновите окончательный ответ в соответствии с текущим ответом на каждом шаге, который фактически дает все возможные допустимые последовательности операций.

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

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