Минимальное количество конфет, необходимое для раздачи детям в зависимости от заданных условий

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

Примеры:

Input: arr[] = {1, 0, 2}
Output: 5
Explanation:
Consider the distribution of candies as {2, 1, 2} that satisfy the given conditions. Therefore, the sum of candies is 2 + 1 + 2 = 5, which is the minimum required candies.

Input: arr[] = {1, 2, 2}
Output: 4

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

• Инициализируйте массив, скажем, ans[] для хранения количества конфет, назначенных каждому дочернему элементу, и инициализируйте его 1 для каждого элемента массива ans[] .
• Пройдите по заданному массиву arr[] и, если значение arr[i + 1] больше, чем arr[i], затем обновите значение ans[i + 1] как ans[i] + 1 .
• Пройдите по данному массиву сзади и выполните следующие шаги:
  • Если значение arr[i] больше, чем arr[i + 1] , а значение ans[i] меньше или равно ans[i + 1] , тогда обновите значение ans[i] как ans[ я + 1] + 1 .
• После выполнения вышеуказанных шагов выведите сумму массива ans[] как результирующую сумму конфет.

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

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