我有一个包含 1,000,000 个整数的列表。每个整数小于或等于 100,000。
我必须找到第一个整数小于第二个整数且第二个整数大于第三个整数的整数之差的最大总和。第三个整数可以小于或大于第一个。此外，第一个整数必须位于第二个之前，第二个整数必须位于第三个之前。
我解决这个问题的算法如下:
1) 通过循环运行提供的列表。
2) 在读取的当前整数之后选择最大的整数。
3) 找出这个和当前整数之间的差异。
4) 选择位于第(2) 部分中的整数之后的最小整数。找出这个整数与第(2)部分中找到的整数之间的差异。
5) 将此添加到第 (3) 部分中找到的整数并将此值存储为当前最大值。
6) 重复此过程并根据需要替换当前最高值。
但是，我解决这个问题的算法没有达到时间限制(每个测试用例 1 秒)。对于一些测试用例，它也是不正确的。我正在使用 C++ 供您引用。
下面提供了一个例子。
输入: 60 70 30 50 40 60 20 10
输出:80
解释:列表中的第三个、第六个和第八个整数最满足条件。
我的问题:解决此问题的最佳(最快)方法是什么？
最佳答案
当前方法的问题
您当前的算法不太正确，请考虑顺序:
1,99,1,100,99
您当前的算法将选择以下情况(不同的情况对应不同的起始位置):
1,100,99 score 100
99,100,99 score 2
1,100,99 score 100
然而，最佳选择是1,99,1，得分为98*2=196
而且复杂度是 O(n^2) 会太慢。
更好的算法
O(n) 的方法是计算一个数组 A[n]，它给出 0,1,..,n-1 范围内的最小值，以及一个数组 B[n]，它给出最小值在 n+1,n+2,..,end 范围内。
您可以在 O(n) 中计算这些，方法是向前遍历数组生成 A，然后向后遍历数组生成 B。
一旦你有了这些，你就可以第三次遍历数组。对于每个索引 i，您为第一个元素选择 A[i]，为中间元素选择 i，为第三个元素选择 B[i]。
你计算出这个组合的分数并保留最好的一个。
(您也可以将其中的几个过程组合起来，以获得稍微复杂但可能更有效的解决方案。)
关于c++ - 找到满足特定条件的整数之间的最大差和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24546002/