通过删除一个数来计算最大点的算法

Question

例1：输入:nums=[3,4,2]输出：6解释：删除4以获得4点，因此3也被删除。然后，删除2个赚取2分。共获得6分。

以下是如何解决它的解释：

算法

public int deleteAndEarn(int[] nums) {
        int[] count = new int[10001];
        for (int x: nums) count[x]++;
        int avoid = 0, using = 0, prev = -1;

        for (int k = 0; k <= 10000; ++k) if (count[k] > 0) {
            int m = Math.max(avoid, using);
            if (k - 1 != prev) {
                using = k * count[k] + m;
                avoid = m;
            } else {
                using = k * count[k] + avoid;
                avoid = m;
            }
            prev = k;
        }
        return Math.max(avoid, using);
    }

我无法理解这里是如何使用avide和using变量的，以及它是如何解决问题语句的。

你能帮我理解这一点吗。

Answer 1

我把那页上的问题看了一遍。该算法基于一个非常好的技巧。当您在应用算法之前首先处理输入时，解决这个问题是非常容易的。输入被重新组织到桶中。

假设您有输入:1 1 2 3 3 2 2 4 4 4

您可以将其重新组织为

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

现在根据这个问题，如果您选择任何桶，您应该放弃包含（bucket-element-value-1）和（bucket-element-value+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] );
}

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 );
 }