Возвращает максимальное значение целого числа по индексу k в массиве
Этот вопрос был задан во время собеседования в Microsoft на должность стажера, я понятия не имею, как к этому подступиться.
Массив состоит из n положительных целых чисел, сумма всех элементов в массиве не превышает max_sum, абсолютная разница между любыми двумя последовательными элементами в массиве не превышает 1. Возвращает максимальное значение целого числа по индексу k в массиве.
Input : n = 3, max_sum = 7, k = 1
Output: 3
In this case let's say array is [2,3,2]
Input: n = 4, max_sum = 6, k = 2
output = 2
In this case let's say array is [1,1,2,1]
Ответы 2
Это метод грубой силы. Лучшим решением было бы вычислить значения, но я оставлю это на ваше усмотрение. Это ваша задача получить работу, верно?
Input: n = 7, max_sum = 34, k = 4
Установите все значения на
0.// ↓ k array = { 0, 0, 0, 0, 0, 0, 0 }, sum = 0Поскольку нам нужно максимальное значение
kс наименьшей суммой, просто увеличьте значение до1.// ↓ k array = { 0, 0, 0, 0, 1, 0, 0 }, sum = 1 (+1)Поскольку последовательные элементы должны быть отделены друг от друга не более чем на
1, когда мы снова увеличиваем значение вk, нам также нужно увеличивать соседние значения.// ↓ k array = { 0, 0, 0, 1, 2, 1, 0 }, sum = 4 (+3)Повторяйте, неоднократно.
// ↓ k array = { 0, 0, 1, 2, 3, 2, 1 }, sum = 9 (+5) array = { 0, 1, 2, 3, 4, 3, 2 }, sum = 15 (+6) array = { 1, 2, 3, 4, 5, 4, 3 }, sum = 22 (+7) array = { 2, 3, 4, 5, 6, 5, 4 }, sum = 29 (+7)Мы не можем повторить еще раз, потому что если бы мы это сделали, то получили бы
sum = 29 + 7 = 36, а это превысило быmax_sum = 34.
Результат: Максимальное значение в k равно 6.
Есть много способов распределить оставшиеся 5 баллов, чтобы получить точную сумму, но показать решение с точной суммой не является целью, поэтому нам не нужно ничего делать с 5 дополнительными баллами.
Определим a как среднее значение массива:
a = max_sum / n
Найдем максимум при k = 0:
max(0) = a + n/2
В этом случае все остальные значения массива будут уменьшаться, поэтому последнее значение будет
a - n/2
для k = 1 мы видим, что максимум не будет превышать max(0)-1, поэтому
max(1) = a + n/2 - 1
и так далее, пока k = n/2. для k > n/2 максимальное значение увеличится до a + n/2 при k = n-1, поэтому мы имеем V-образную кривую с минимумом при k=n/2, равным a.
Осталось только правильно обработать граничные условия, нечетные или четные n и так далее. Надеюсь, вы уловили идею.
Хорошо спасибо! Я имел в виду, что нет необходимости в итерациях или грубой силе :)
Тогда вы должны отредактировать ответ и сказать это вместо этого.
«В алгоритме нет необходимости» Википедия определяет алгоритм как «конечную последовательность четко определенных, реализуемых компьютером инструкций». Merriam-Webster определяет его как «процедуру решения математической задачи (например, нахождения наибольшего общего делителя) за конечное число шагов, которая часто включает повторение операции». Обратите внимание, что повторение не требуется. Таким образом,
a = max_sum / n— это алгоритм. Любая математическая формула, реализуемая компьютером, является алгоритмом.