algorithm - 最大化输入中不超过 k 个连续元素的列表总和

Question

我有一个由 N 个数字组成的数组，我只想从列表中删除那些元素，删除这些元素后将创建一个新列表，其中不再有 K 个数字相邻对彼此。可以使用此限制创建多个列表。所以我只想要一个列表，其中剩余数字的总和最大，并作为输出仅打印该总和。

到目前为止我提出的算法的时间复杂度为 O(n^2)。是否有可能获得更好的算法来解决这个问题？

Link to the question .

这是我的尝试:

int main()
{
    //Total Number of elements in the list
    int count = 6;
    //Maximum number of elements that can be together
    int maxTogether = 1;

    //The list of numbers
    int billboards[] = {4, 7, 2, 0, 8, 9};

    int maxSum = 0;
    for(int k = 0; k<=maxTogether ; k++){
        int sum=0;
        int size= k;

        for (int i = 0; i< count; i++) {
            if(size != maxTogether){
                sum += billboards[i];
                size++;
            }else{
                size = 0;
            }
        }
        printf("%i\n", sum);
        if(sum > maxSum)
        {
            maxSum = sum;
        }
    }
    return 0;
}

Answer 1

O(NK) dynamic programming解决方案相当简单:

设 A[i] 为左侧受非k-连续约束约束的元素的最佳总和(假设我们要删除 >i-th 元素也是如此)。

然后我们可以通过回顾K个元素来计算A[i]:

A[i] = 0;
for j = 1 to k
  A[i] = max(A[i], A[i-j])
A[i] += input[i]

最后，只需查看 A 中的最后 k 个元素，将元素添加到每个元素的右侧，然后选择最好的一个。

但这太慢了。

让我们做得更好。

因此，A[i] 从 A[i-1]、A[i-2]、... 中找到最好的，A[i-K+1]，A[i-K]。
因此，A[i+1] 从 A[i]、A[i-1]、A[i -2]，...，A[i-K+1]。

那里有很多冗余 - 由于 A[i]，我们已经从索引 i-1 到 i-K 中知道了最好的信息。 s 计算，但随后我们在 A[i+1] 中再次找到除了 i-K(使用 i)之外的所有计算中最好的。

因此，我们可以将它们全部存储在有序数据结构中，然后删除 A[i-K] 并插入 A[i]。我的选择-A binary search tree找到最小值，以及 circular array树节点大小为K+1，因此我们可以轻松找到需要删除的节点。

我交换了问题的位置，使其变得稍微简单一些 - 我没有找到剩余元素的最大值，而是找到了删除元素的最小值，然后返回总和 - 删除的总和。

高级伪代码:

for each i in input
  add (i + the smallest value in the BST) to the BST
  add the above node to the circular array
    if it wrapper around, remove the overridden element from the BST

// now the remaining nodes in the BST are the last k elements

return (the total sum - the smallest value in the BST)

运行时间:

O(n log k)

Java 代码:

int getBestSum(int[] input, int K)
{
   Node[] array = new Node[K+1];
   TreeSet<Node> nodes = new TreeSet<Node>();
   Node n = new Node(0);
   nodes.add(n);
   array[0] = n;
   int arrPos = 0;
   int sum = 0;
   for (int i: input)
   {
      sum += i;
      Node oldNode = nodes.first();
      Node newNode = new Node(oldNode.value + i);
      arrPos = (arrPos + 1) % array.length;
      if (array[arrPos] != null)
         nodes.remove(array[arrPos]);
      array[arrPos] = newNode;
      nodes.add(newNode);
   }
   return sum - nodes.first().value;
}

getBestSum(new int[]{1,2,3,1,6,10}, 2) 根据需要打印 21。