11

给你一个包含 n 个数字的列表L=<a_1, a_2,...a_n>。它们中的每一个都是 0 或 +/- 2 k , 0 <= k <= 30 的形式。描述并实现一个返回 CONTINUOUS SUBLIST 的最大乘积的算法 p=a_i*a_i+1*...*a_j, 1 <= i <= j <= n。

例如，对于输入<8 0 -4 -2 0 1>，它应该返回 8（8 或 (-4)*(-2)）。

您可以使用任何标准编程语言，并且可以假设列表以任何标准数据结构给出，例如int[], vector<int>,List<Integer>等。

你的算法的计算复杂度是多少？

4

7 回答 7

6

在我的第一个答案中，我解决了 OP 的“将两个大数相乘”的问题。事实证明，这个愿望只是我现在要解决的更大问题的一小部分：

“我还没有达到我算法的最终框架，我想知道你是否可以帮助我解决这个问题。”

（问题描述见问题）

我要做的只是更详细地解释Amnon 提出的方法，所以所有的功劳都应该归功于他。

您必须从 2 的幂的整数列表中找到连续子列表的最大乘积。这个想法是：

  1. 计算每个连续子列表的乘积。
  2. 返回所有这些产品中最大的一个。

start您可以通过其和end索引来表示子列表。因为start=0有 n-1 个可能的值end，即 0..n-1。这将生成从索引 0 开始的所有子列表。在下一次迭代中，您递增start1 并重复该过程（这一次，有 n-2 个可能的值end）。这样您就可以生成所有可能的子列表。

现在，对于这些子列表中的每一个，您必须计算其元素的乘积——即提出一个方法computeProduct(List wholeList, int startIndex, int endIndex)。您可以使用内置BigInteger类（它应该能够处理您的作业提供的输入）来使您免于进一步的麻烦，或者尝试实现其他人描述的更有效的乘法方式。（我将从更简单的方法开始，因为它更容易查看您的算法是否正常工作，然后首先尝试优化它。）

现在您可以遍历所有子列表并计算其元素的乘积，确定具有最大乘积的子列表应该是最简单的部分。

如果您仍然难以在两个步骤之间建立联系，请告诉我们 - 但也请在您解决问题时向我们提供您的代码草稿，这样我们就不会最终逐步构建解决方案而您复制和粘贴它。

编辑：算法骨架

public BigInteger listingSublist(BigInteger[] biArray)
{       
    int start = 0;
    int end = biArray.length-1;
    BigInteger maximum;

    for (int i = start; i <= end; i++)
    {
        for (int j = i; j <= end; j++)
        {
            //insert logic to determine the maximum product.
            computeProduct(biArray, i, j);
        }
    }

    return maximum;                
}

public BigInteger computeProduct(BigInteger[] wholeList, int startIndex, 
                                                         int endIndex)
{
    //insert logic here to return
    //wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
    //    wholeList[endIndex]);       
}
于 2010-07-18T16:20:23.260 回答
4

由于 k <= 30，任何整数 i = 2 k都适合 Java int。然而，这两个整数的乘积可能不一定适合 Java int，因为 2 k * 2 k = 2 2*k <= 2 60填充到 Javalong中。这应该回答您关于“（乘以）两个数字......”的问题。

如果您可能想要将两个以上的数字相乘，您的作业暗示“...连续子列表的最大乘积...”（子列表的长度可能 > 2），请查看 Java 的BigInteger类.

于 2010-07-18T15:05:52.530 回答
4

实际上，最有效的乘法方法是加法。在这种特殊情况下，您所拥有的只是 2 的幂的数字，您可以通过简单地将指数相加来获得子列表的乘积（并计算乘积中的负数，并在奇数的情况下将其设为负数底片）。

当然，要存储结果，您可能需要 BigInteger，如果您用完了位。或者根据输出的外观，只需说 (+/-)2^N，其中 N 是指数的总和。

解析输入可能是 switch-case 的问题，因为您只有 30 个数字需要处理。加上底片。

那是无聊的部分。有趣的部分是如何获得产生最大数字的子列表。您可以通过检查每一个变化来采取愚蠢的方法，但在最坏的情况下（IIRC）这将是一个 O(N^2) 算法。对于较长的输入，这确实不是很好。

你能做什么？我可能会从列表中最大的非负数作为子列表开始，然后扩展子列表以在每个方向上获得尽可能多的非负数。然后，在所有正面都触手可及的情况下，继续在两侧进行成对的底片，例如。只有当你可以在列表的两边都增长时才会增长。如果您不能双向增长，请尝试使用两个（四个、六个等，甚至是偶数）连续负数的方向。如果你连这种方式都不能成长，那就停下来。

好吧，我不知道这个算法是否有效，但如果它（或类似的东西）有效，它是一个 O(N) 算法，这意味着很好的性能。让我们试试吧！:-)

于 2010-07-18T15:37:03.913 回答
3

编辑：我调整了算法大纲以匹配实际的伪代码，并将复杂性分析直接放入答案中：

算法概要

依次遍历序列并存储自最后一个 0 以来产品（正）的值和第一个/最后一个索引。对另一个产品（负）执行相同操作，该产品仅包含自序列的第一个符号更改以来的数字。如果您遇到负序列元素，则交换两个产品（正数和负数）以及关联的起始索引。每当正积达到新的最大值时，就会存储它和相关的开始和结束索引。遍历整个序列后，结果存储在最大变量中。

为避免溢出以二进制对数和附加符号计算。

伪代码

maxProduct = 0
maxProductStartIndex = -1
maxProductEndIndex = -1
sequence.push_front( 0 ) // reuses variable intitialization of the case n == 0

for every index of sequence
   n = sequence[index]
   if n == 0
       posProduct = 0
       negProduct = 0
       posProductStartIndex = index+1
       negProductStartIndex = -1
   else
       if n < 0
           swap( posProduct, negProduct )
           swap( posProductStartIndex, negProductStartIndex )
           if -1 == posProductStartIndex // start second sequence on sign change
               posProductStartIndex = index
           end if
           n = -n;
       end if
       logN = log2(n) // as indicated all arithmetic is done on the logarithms
       posProduct += logN
       if -1 < negProductStartIndex // start the second product as soon as the sign changes first
          negProduct += logN
       end if
       if maxProduct < posProduct // update current best solution
          maxProduct = posProduct
          maxProductStartIndex = posProductStartIndex
          maxProductEndIndex = index
       end if
   end if
end for

// output solution

print "The maximum product is " 2^maxProduct "."
print "It is reached by multiplying the numbers from sequence index " 
print maxProductStartIndex " to sequence index " maxProductEndIndex

复杂

该算法在序列上使用单个循环，因此它的 O(n) 乘以循环体的复杂度。body最复杂的操作是log2。因此，它的 O(n) 是 log2 的复杂度的倍数。一些有界大小的 log2 是 O(1)，因此得到的复杂度是 O(n)，也就是线性的。

于 2010-07-18T15:04:18.117 回答
3

嗯..因为它们都是 2 的幂，你可以只添加指数而不是乘以数字（相当于取乘积的对数）。例如，2^3 * 2^7 是 2^(7+3)=2^10。我将把处理标志作为练习留给读者。

关于子列表问题，有少于 n^2 对 (begin,end) 索引。您可以全部检查，或尝试动态编程解决方案。

于 2010-07-18T15:34:17.973 回答
1

我想将 Amnon 关于 2 的乘方的观察与我关于子列表的观察结合起来。

列表以 0 硬终止。我们可以将问题分解为在每个子列表中找到最大的产品，然后找到其中的最大值。（其他人已经提到了这一点）。

这是我对这篇文章的第三次修订。但是3的魅力...

方法

给定一个非 0 数字的列表，（这需要很多思考）有 3 个子案例：

  1. 该列表包含偶数个负数（可能为 0）。这是微不足道的情况，最佳结果是所有数字的乘积，保证为正。

  2. 该列表包含奇数个负数，因此所有数字的乘积都是负数。为了改变符号，有必要牺牲一个包含负数的子序列。两个子案例：

    一种。牺牲从左到右的数字，包括最左边的负数；或者

    湾。牺牲从右到右的数字，包括最右边的负数。

    在任何一种情况下，返回剩余数字的乘积。只牺牲了一个负数，结果肯定是正数。选择 (a) 和 (b) 的获胜者。

执行

输入需要拆分为以 0 分隔的子序列。如果构建驱动程序方法来循环遍历列表并挑选非 0 序列的开头和结尾，则可以就地处理列表。

以多头进行数学运算只会使可能的范围增加一倍。转换为 log2 使大乘积的算术运算更容易。它可以防止在大数的大序列上出现程序故障。或者，也可以在 Bignums 中进行所有数学运算，但这可能会表现不佳。

最后，最终的结果，仍然是一个 log2 数字，需要转换成可打印的形式。Bignum 在那里派上用场。有new BigInteger("2").pow(log);这将提高 2 的幂 log。

复杂

该算法通过子列表顺序工作，每个子列表只处理一次。在每个子列表中，将输入转换为 log2 并将结果转换回来是一项烦人的工作，但工作量与列表的大小成线性关系。在最坏的情况下，列表的大部分总和被计算两次，但这也是线性复杂度。

于 2010-07-18T19:00:56.500 回答
1

请参阅此代码。在这里，我实现了大量的精确阶乘。我只是使用整数数组来制作大数字。从Planet Source Code下载代码。

于 2010-07-19T17:24:46.667 回答