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

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

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

  • Выберите любой элемент (скажем, k ) из массива и увеличьте все остальные элементы на 1 .
  • На следующем шаге переходим только к индексу со значением k+1 .
  • В конце концов, вы находитесь на максимальном значении.

Примеры:

Input: N = 4, arr[] ={1, 2, 1, 3}
Output: 3
Explanation: If started from index 0 with a height of 1 unit, then,  
the new value of array will be [1, 3, 2, 4]. 
Then jump to the index with (1+1 = 2) ie 2nd index,  
The updated values are [2, 4, 2, 5]. Cannot be at the maximum value at end
The first chosen value was 3 at index 3. 
The updated values are [2, 3, 2, 3]. Max achieved -3. Hence ans = 3;

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

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

On observation, we can realize that for reaching maximum height we have two options

  • Directly selecting the maximum heighted podium initially available.
  • Choosing all the elements (say total y) with same value (say x). So highest number that can be reached is (x + y – 1).

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

  • Отсортируйте массив в порядке возрастания.
  • Найдите диапазон одинаковых элементов значения и получите максимальное значение , которое может быть достигнуто из этого диапазона, используя приведенную выше идею.
  • Выполните это для всех доступных диапазонов и сохраните максимум.
  • Верните максимум как требуемый ответ.

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

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

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