algorithm - 找到一个巨大的整数集的最大子集

Question

我在 .txt 文件中有一大组 (S) 长无符号整数。如何找到具有以下属性的 S 的最大子集 (Pmax):

P{X1,X2,X3,...,Xn) | X1>=(Xn/4)

更多详情:

1. 当我说最大子集时，我指的是元素数量最多的子集 (n->max)。
2. 由于内存有限，我无法将 .txt 加载到数组中。
3. 我的系统内存是200MB
4. txt 文件有 10^6 个整数。每个整数可以是 long unsigned 32bit。
5. 我需要找到 S 的最大子集，条件是:

X1 < X2 < X3 < ... < Xn-1 < Xn 如 X1 >= (XN/4)

例如，如果 txt 文件具有以下内容:15,14,13,4,2,2,3,10,1,2,2那么这些是可能的子集:

P1(4,10,13,14,15)

P2(3,4,10)

P3(1,2,2,2,2,3,4)

所以 Pmax(1,2,2,2,2,3,4) 因为它有更多的元素。

事实上，我不想准确地找到 Pmax。我只想找到子集 Pmax 的元素数。所以这里是 7。

算法应该非常快。

我不会找人来做我的工作。我只需要一个相应的问题，这样我就可以寻找有效的解决方案。提前致谢!!!

Answer 1

假设您的条件意味着“子集中的所有元素都大于 X1 除以 4”，您需要 2 个简单的嵌套循环和一些辅助变量。

在伪代码中，像这样的东西应该可以工作:

var idx = 0, largest = 0, currentIdx = 0;

while(var current = getIntegerFromFileById(currentIdx))
{
  var size = 1;
  while(getIntegerFromFileById(currentIdx + size++) > current / 4);
  if(size > largest) {
    idx = currentIdx;
    largest = size;
  }
  currentIdx++;
}
print "Longest subset is at index {idx}.";
print "It contains {largest} consecutive elements.";

这也是事实上的最优实现。最明显的优化是在扫描期间将整数逐步加载到内存缓冲区中，以防止双重 I/O 操作。

如果我误解了条件，这应该仍然很容易适应大多数其他条件，周围的算法保持不变，您只需修改内部 while 中的条件。