Алгоритм вычисления максимума баллов путем удаления числа

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

Допустим, у вас есть ввод: 1 1 2 3 3 2 2 4 4 4

Вы можете реорганизовать его в

(Two 1s), (Three 2s), ( Two 3s), (Three 4s)

Теперь, согласно проблеме, если вы выберете любое ведро, вы должны отказаться от ведра, содержащего (значение-элемента-ведра - 1) и (значение-элемента-ведра + 1), которые фактически являются смежными с этим ведром.

Проблема теперь сводится к тому, как бы вы выбрали сегменты, чтобы получить максимальную сумму с учетом того ограничения, что вы не можете получить значения соседних сегментов?

Это просто - по мере того, как вы просматриваете ведра, вы можете сделать с ним две вещи. Либо избегайте этого, либо используйте.

Если вы этого избегаете, то какой максимальной суммы вы можете достичь - это зависит от того, что вы сделали с предыдущим.

amountWhenAvoided[i] = Math.max( amountWhenAvoided[i-1], amountWhenTaken[i-1] );

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

amountWhenTaken[i] = amountWhenAvoided[i-1] + valueOfBucket[i]

Как только вы дойдете до конца корзин, ответ будет:

Math.max( amountWhenTaken[n], amountWhenAvoided[n] )

Вы можете закодировать это так:

public int deleteAndEarn( int[] nums ) {
  //reorganize.
  int[] valueOfBucket= new int[10001] //This is the maximum size of the buckets.

  for ( int num : nums ) {
     valueOfBucket[num] += num; //Populate each bucket.
  }

  //Now go through each bucket - remember - a bucket could be empty that's fine.
  int[] amountWhenTaken = new int[n];
  int[] amountWhenAvoided = new int[n];
  amountWhenTaken[0] = 0; //Because there are no buckets to start with - buckets start from 1
  amountWhenAvoided[0] = 0;
  for ( int i = 1; i <= n; i++ ) {
     amountWhenAvoided[i] = Math.max( amountWhenAvoided[i-1], amountWhenTaken[i-1] );
     amountWhenTaken[i] = amountWhenAvoided[i-1] + valueOfBucket[i];
  }
  return Math.max( amountWhenTaken[n], amountWhenAvoided[n] );
}

Если вы обратите внимание на приведенный выше код, то с массивами это действительно не нужно. Поскольку текущий элемент в массиве зависит от его предыдущего элемента, поэтому мы можем сделать это всего с двумя переменными, назовем их avoiding, using Тогда второй цикл for можно записать как:

public int deleteAndEarn( int[] nums ) {
      //reorganize.
      int[] valueOfBucket= new int[10001] //This is the maximum size of the buckets.

      for ( int num : nums ) {
         valueOfBucket[num] += num; //Populate each bucket.
      }

      //Now go through each bucket - remember - a bucket could be empty that's fine.
      int using_prev = 0;
      int avoiding_prev = 0;
      int avoiding_curr = 0;
      int using_curr = 0;
      for ( int i = 1; i <= n; i++ ) {
         avoiding_curr = Math.max( avoiding_prev, using_prev);
         using_curr = avoiding_prev + valueOfBucket[i];
         avoiding_prev = avoiding_curr;
         using_prev = using_curr;
      }
      return Math.max( avoiding_curr, using_curr );
 }