Bezdepbonusu7Программирование: статьи и ответы
Меню

Вопрос

Длина самого длинного подмассива со всеми одинаковыми элементами

Автор вопроса: go_kОтветов: 2

У меня есть проблема:

Вам задан массив целых чисел A и целое число k. Вы можете уменьшить элементы массива A до k раз, чтобы создать последовательный подмассив, все элементы которого равны. Возвратите длину максимально возможного последовательного подмассива, который вы можете создать таким образом.

Например, если A равно [1,7,3,4,6,5], а k равно 6, вы можете получить [1,7,3,4 -1,6-1-1-1,5-1-1] = [1,7,3,3,3,3], поэтому вы вернете 4.

Какое оптимальное решение?

  • Можете ли вы объяснить пример? почему 4? Shridhar R Kulkarni 19.12.2020
  • [3 4 6 5] подмассив [3,3+1,3+3,3+2] стоимость уменьшения равна 6, чтобы сделать все элементы равными go_k 19.12.2020
  • Какова максимальная длина исходного массива? VFX 19.12.2020
  • N - длина исходного массива, а K - стоимость go_k 19.12.2020
  • Да, я знаю, но я имею в виду, каково максимальное значение N? VFX 19.12.2020
  • Каков ваш подход к грубой силе? Shridhar R Kulkarni 19.12.2020

algorithm

Ответы

Ответ 1 · рейтинг 3 · גלעד ברקן

Подмассив должен быть сделан равным своему младшему элементу, поскольку единственной допустимой операцией является сокращение (а уменьшение самого нижнего элемента приведет к дополнительным затратам). Дано:

a1, a2, a3...an

стоимость снижения составляет:

sum(a1..an) - n * min(a1..an)

Например,

3, 4, 6, 5
sum = 18
min = 3
cost = 18 - 4 * 3 = 6

Один из способов уменьшить сложность с O(n^2) до логарифмического коэффициента: для каждого элемента как самого правого (или самого левого) элемента подмассива-кандидата наилучший двоичный поиск наибольшей длины в пределах стоимости. Для этого нам нужна только сумма, которую мы можем получить из суммы префиксов за O(1), длина (по которой мы уже ищем) и запрос минимального диапазона, который хорошо изучен.

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

Код JavaScript:

function cost(A, i, j){
  const n = j - i + 1;
  let sum = 0;
  let min = Infinity;
  for (let k=i; k<=j; k++){
    sum += A[k];
    min = Math.min(min, A[k]);
  }
  return sum - n * min;
}

function f(A){
  for (let j=0; j<A.length; j++){
    const rightmost = A[j];
    const sequence = [];

    for (let i=j; i>=0; i--)
      sequence.push(cost(A, i, j));

    console.log(rightmost + ': ' + sequence);
  }
}

var A = [1,7,3,1,4,6,5,100,1,4,6,5,3];

f(A);

Ответ 2 · рейтинг 1 · Ashutosh Bichare

def cost(a, i, j):
  n = j - i
  s = 0
  m = a[i]
  for k in range(i,j):
    s += a[k]
    m = min(m, a[k])
  return s - n * m;

def solve(n,k,a):
 m=1
 for i in range(n):
  for j in range(i,n+1):
   if cost(a,i,j)<=k:
    x = j - i
    if x>m:
     m=x
 return m

Это мое решение python3 в соответствии с вашими спецификациями.

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Похожие материалы