Максимизируйте значение K так, чтобы подпоследовательность с суммой i существовала для каждого целого числа i в диапазоне [1, K]

Опубликовано: 22 Сентября, 2022

Для данного массива arr[] , состоящего из N целых чисел, задача состоит в том, чтобы найти максимальное значение K такое, что для каждого целого числа i в диапазоне [1, K] существует подпоследовательность, сумма которой равна i .

Примеры:

Input: arr[] = {1, 2, 1, 3}
Output: 7
Explanation:
Below are the possible values of the sum for all the subsequences that can be formed:

  1. Subsequence {1}, the sum of elements is 1.
  2. Subsequence {2}, the sum of elements is  2.
  3. Subsequence {3}, the sum of elements is 3.
  4. Subsequence {1, 3}, the sum of elements is 4.
  5. Subsequence {1, 1, 3}, the sum of elements is 5.
  6. Subsequence {1, 2, 3}, the sum of elements is 6.
  7. Subsequence {1, 1, 2, 3}, the sum of elements is 7.

Hence, the maximum value of K is 7. Hence print 7.

Input: arr[] = {2, 5, 2, 3}
Output: 0

Подход: выполните следующие шаги, чтобы решить данную проблему:

  • Отсортируйте данный массив arr[] .
  • Инициализируйте переменную, скажем, next как 0 , чтобы сохранить результирующее максимальное значение K .
  • Пройдите массив arr[] по диапазону [0, N – 1] и выполните следующие шаги:
    • Если значение arr[i] меньше или равно (next + 1) , то подпоследовательности {0, 1, 2, …, next + arr[i]} могут быть сгенерированы с использованием элементов массива. Поэтому добавьте значение arr[i] в переменную next .
    • В противном случае выйти из цикла, так как сумма (next + 1) не может быть сгенерирована какой-либо подпоследовательностью массив, все значения, за которыми следует arr[i] , больше этого.
  • После выполнения вышеуказанных шагов выведите значение следующего как результирующее максимальное значение K .

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ