2

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

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

链接到问题。

这是我的尝试：

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

3 回答 3

2

O(NK) 动态规划解决方案相当简单：

让A[i]成为受非连续约束的左侧元素的最佳总和k（假设我们也删除了i第 -th 个元素）。

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

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

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

但这太慢了。

让我们做得更好。

所以从, , ..., ,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]

那里有很多冗余——我们已经从索引中知道了最好的，i-1因为i-K'的A[i]计算，但是我们在.i-KiA[i+1]

所以我们可以将它们全部存储在一个有序的数据结构中，然后删除A[i-K]和插入A[i]。我的选择 -找到最小值的二叉搜索树，以及树节点大小的圆形数组K+1，因此我们可以轻松找到需要删除的那个。

我交换了问题以使其稍微简单一些 - 我没有找到剩余元素的最大值，而是找到移除元素的最小值，然后返回total sum - removed sum。

高级伪代码：

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，根据需要。

于 2013-10-12T20:23:28.517 回答
0

以下算法的复杂度为 O(N*K)。

检查数组的第一个 K 元素（0 到 K-1）。该区域最多可以有 1 个间隙。
原因：如果有两个差距，那么没有任何理由有更低的（早期差距）。

For each index i of these K gap options, following holds true:  
 1. Sum upto i-1 is the present score of each option.  
 2. If the next gap is after a distance of d, then the options for d are (K - i) to K  

For every possible position of gap, calculate the best sum upto that position among the options.  
The latter part of the array can be traversed similarly independently from the past gap history.

进一步遍历数组直到结束。

于 2013-10-12T17:50:44.977 回答
0

让f[i]成为您可以使用前 i 个数字获得的最大总值，而您不选择最后一个（即第 i 个）。然后我们有

f[i] = max{
           f[i-1],
           max{f[j] + sum(j + 1, i - 1) | (i - j) <= k}
          }

您可以使用类似heap的数据结构来维护选项并及时获得最大值log(n)，保持全局delta或其他，并注意范围i - j <= k。

于 2013-10-12T17:28:59.123 回答