Максимизируйте индексы со значением, превышающим сумму соседей

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

Учитывая массив целых чисел arr[] , задача состоит в том, чтобы найти максимальное количество индексов, имеющих значения, превышающие сумму соседей после выполнения данной операции:

  • В операции вы можете выбрать K (данные) последовательных элементов и увеличить их значения на 1.
  • Эту операцию можно выполнять любое количество раз

Примеры:

Input: arr[] = [2, 9, 2, 4, 1], K = 2
Output: 2
Explanation: Here arr[1] and arr[3] is fulfilling the criteria.
No matter how many times you increase K consecutive elements,
you cannot get more than 2 such indices.

Input: arr[] = [3, 1, 3, 4, 5, 1, 2], K = 1
Output: 3
Explanation: We will select K =1 consecutive elements and increment it’s value by 1
Select arr[1] six times then array becomes: [3, 7, 3, 4, 5, 1, 2]
Select arr[3] five times then array becomes: [3, 7, 3, 9, 5, 1, 2]
Select arr[5] seven times then array becomes: [3, 7, 3, 9, 5, 8, 2]
Now arr[1], arr[3] and arr[5] satisfies the criteria.

Подход: Чтобы решить проблему, следуйте следующей идее:

This problem deals with finding the maximum count of indices, after performing the given operation any number of times. 

Here, if K = 1, then the answer will be equal to the number of elements present at the odd index, 
If K > 1 then the answer will be equal to the number of indices that already satisfies the given criteria, as increasing the values of a subarray can never help to get a new index, as the values of its neighbors will also increase.

Выполните указанные шаги, чтобы решить проблему:

  • Если К = 1 , тогда ответом будет количество элементов, присутствующих в нечетном индексе в arr[]
  • Для других значений K здесь ответом будут те индексы, у которых arr[i] > arr[i + 1] + arr[i – 1].
  • Возвращает количество в зависимости от значения K .

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

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

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