Минимальное количество индексов, которые нужно пропустить для каждого индекса массива, чтобы сохранить сумму до этого индекса не более T

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

Примеры:

Input: N = 7, T = 15, arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 0 0 0 0 0 2 3 
Explanation: No indices need to be skipped for the first 5 indices: {1, 2, 3, 4, 5}, since their sum is 15 and <= T.
For the sixth index, indices 3 and 4 can be skipped, that makes its sum = (1+2+3+6) = 12.
For the seventh, indices 3, 4 and 5 can be skipped which makes its sum = (1+2+3+7) = 13.

Input: N = 2, T = 100, arr[] = {100, 100}
Output: 0 1

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

• Создайте упорядоченную карту M , чтобы вести подсчет элементов до i -го индекса.
• Инициализируйте переменную sum как 0 , чтобы сохранить сумму префикса.
• Пройдите массив, arr[] используя переменную i
  • Сохраните разницу между sum+arr[i] и T в переменной d .
  • Если значение d>0 , пройдите карту с конца и выберите индексы с самыми большими элементами, пока сумма не станет меньше T . Сохраните необходимое количество элементов в переменной k .
  • Добавьте arr[i] к сумме и увеличьте A[i] в M на 1 .
  • Выведите значение k .

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

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