logo标签列表

寻找最大值

c++algorithm
4

Given an integer n and array a. Finding maximum of (a[i]+a[j])*(j-i) with 1<=i<=n-1 and i+1<=j<=n

Example:

Input

5
1 3 2 5 4

Output

21

Explanation :With i=2 and j=5, we have the maximum of (a[i]+a[j])*(j-i) is (3+4)*(5-2)=21

Constraints:

n<=10^6
a[i]>0 with 1<=i<=n

对于n<=10^4，我可以解决这个问题，但是如果n过大，比如约束条件怎么办？

你是不是指的是“最大值”（而不是“maximine”）？你有实际问题吗？你有一个程序吗？有什么问题吗？Stack Overflow不是编程服务。既然你已经在这里注册了一个月，你应该意识到这一点。 - paddy
1
为什么你只能处理不到100,000个数字？你不需要将所有数字存储在堆栈上 - 你可以动态分配内存。请展示你的程序，这样我们才能提出真正的建议。 - Jerry Jeremiah
1
你能否把在 n < 10^4 下运行的代码粘贴一下？ - Nimrod
3
我认为OP想要表达的意思是，当N变得很大时，迭代每个i和j的所有可能组合的N平方解决方案会很快遇到瓶颈。有一个不明显的解决方法，可能涉及二叉树或排序数组，但我还不确定。等我有更多时间，我可能会回来看看这个问题。 - selbie
3个回答
4
首先，让我们参考“暴力”算法。下面我会指出其中的一些问题，但这是一个正确的解决方案。
struct Result
{
    size_t i;
    size_t j;
    int64_t value;
};

Result findBestBruteForce(const vector<int>& a)
{
    size_t besti = 0;
    size_t bestj = 0;
    int64_t bestvalue = INT64_MIN;

    for (size_t i = 0; i < a.size(); i++)
    {
        for (size_t j = i + 1; j < a.size(); j++)
        {
            // do the math in 64-bit space to avoid overflow
            int64_t value = (a[i] + (int64_t)a[j]) * (j - i);
            if (value > bestvalue)
            {
                bestvalue = value;
                besti = i;
                bestj = j;
            }
        }
    }
    return { besti, bestj, bestvalue };
}

以上代码的问题在于其时间复杂度为O(N²)。更确切地说，对于外部for循环的N次迭代（其中i从0到N），内部for循环平均会迭代N/2次。如果N很小，这并不是问题。
在我的PC上，打开了全部优化后，当N小于20000时，运行时间不到1秒钟。一旦N接近100000，处理50亿次迭代需要几秒钟。让我们假设预期速率为每秒10亿次操作。如果N为1000000，即OP所概述的最大值，可能需要500秒。这就是N平方算法的本质。
那么我们该如何加快速度呢？这里有一个有趣的观察。假设我们的数组是这样的：
10 5 4 15 13 100 101 6
在上面的外部循环的第一次迭代中，其中i=0，我们将在内部循环的每次迭代中计算以下内容：
for each j: (a[0]+a[j])(j-0)
for each j: (10+a[j])(j-0)
for each j: [15*1, 14*2, 25*3, 23*4, 1000*5, 1010*6, 16*6]
         =  [15,     28,   75,   92,   5000,   6060,   96]

因此，当i=0时，a[i]=15，从该集合计算出的最大值为6060。
由于A[0]为15，并且我们正在跟踪当前的“最佳”值，因此没有动力再次迭代所有值以获取i=1，因为a[1]==14小于15。 没有j索引可以计算出比已经找到的更大的(a[1]+a[j])*(j-1)的值。 因为(14+a[j])*(j-1)将始终小于(15+a[j])*(j-1)。（假定数组中的所有值均为非负数）。
因此，要进行概括，外循环可以跳过任何i索引处的A[best_i]>A[i]。 这是对上述代码的一个非常简单的改变：
Result findBestOptimized(const std::vector<int>& a)
{

    if (a.size() < 2)
    {
        return {0,0,INT64_MIN};
    }

    size_t besti = 0;
    size_t bestj = 0;
    int64_t bestvalue = INT64_MIN;
    int minimum = INT_MIN;

    for (size_t i = 0; i < a.size(); i++)
    {
        if (a[i] <= minimum)
        {
            continue;
        }

        for (size_t j = i + 1; j < a.size(); j++)
        {
            int64_t value = (a[i] + (int64_t)a[j]) * (j - i);
            if (value > bestvalue)
            {
                bestvalue = value;
                besti = i;
                bestj = j;
                minimum = a[i];
            }
        }
    }

    return { besti, bestj, bestvalue };
}

上面，我们介绍了在考虑进行完整的内部循环枚举之前，A[i]必须达到的最小值。

我使用编译优化对其进行了基准测试。在一个一百万项的随机数组上，它在不到一秒的时间内运行。

但是...还有另一个优化!

如果内部循环未能找到一个索引j使得value>bestvalue，则我们已经知道当前的A[i]大于minimum。因此，在内部循环结束时，我们可以将minimum增加到A[i]。

现在，我将呈现最终解决方案：

Result findBestOptimizedEvenMore(const std::vector<int>& a)
{

    if (a.size() < 2)
    {
        return { 0,0,INT64_MIN };
    }

    size_t besti = 0;
    size_t bestj = 0;
    int64_t bestvalue = INT64_MIN;
    int minimum = INT_MIN;

    for (size_t i = 0; i < a.size(); i++)
    {
        if (a[i] <= minimum)
        {
            continue;
        }

        for (size_t j = i + 1; j < a.size(); j++)
        {
            int64_t value = (a[i] + (int64_t)a[j]) * (j - i);
            if (value > bestvalue)
            {
                bestvalue = value;
                besti = i;
                bestj = j;
            }
        }
        minimum = a[i]; // since we know a[i] > minimum, we can do this

    }

    return { besti, bestj, bestvalue };
}

我对上述解决方案进行了基准测试，数组大小从N = 100到N = 1000000不等。它可以在不到25毫秒的时间内完成所有迭代。

在上述解决方案中，当数组中的所有项按升序排列时，可能存在O（N²）的最坏情况运行时间。但我认为平均情况应该是O（N lg N）或更好的顺序。如果有人感兴趣，我会稍后进行更多分析。

这确实是Theta(n^2)的最坏情况。平均情况比这个要少，最多为O(n^(3/2))，但可能更好。在随机排列的整数数组上的预期运行时间也可以降至O(n)（如果您知道它是升序，则所有升序数组都可以在常数时间内解决）。 - kcsquared
你的 minimum 变量在从左到右的遍历中取得了迄今为止看到的最大值，直到它看到全局最大值 M。如果你从右到左这样做，你也会得到一个以 M 结尾的递增序列。这两个序列形成了一个单峰（严格递增，然后严格递减）序列。这个问题的最优解始终来自选择一个端点在 M 左侧或左边，另一个端点在 M 右侧或右边。由于最长递增子序列的预期大小是 O(sqrt(n))，因此在这个子序列上的平均运行时间可能是 O(n)。 - kcsquared
1
@kcsquared - 如果你有解决方案，我很想看看。OP 也可能会喜欢。你考虑发表一个答案吗？我不确定你提到这个作为子序列问题的参考是什么意思。 - selbie
我会发布一个完整的答案 - 我一直在等待找到一个次二次最坏情况解决方案，但看起来不太可能。它使用了您的技术，但也预先从右到左计算“最小值”序列。 - kcsquared
3
注意：代码中的一些变量符号和 Result 类已从 @selbie 的 出色 的回答中复制而来。
以下是另一种时间复杂度为 O(n^2) 的最差情况解法，对于随机排列可能有可证明的期望 O(n) 性能，并提供了优化空间。
假设 [i, j] 是我们最优解的数组边界。根据问题定义，这意味着所有位于 i 左侧的元素必须严格小于 A[i]，而所有位于 j 右侧的元素必须严格小于 A[j]。
这意味着我们可以计算 A 的左极大值：所有严格大于前面元素的元素，以及 A 的右极大值。然后，我们只需要考虑左极大值的左端点和右极大值的右端点。
我不知道左和右极大值集大小乘积的期望，但我们可以得到一个上界。左极大值的大小至多为 A 的最长上升子序列（LIS）大小。右极大值至多为最长下降子序列的大小。这些不是独立的，但我认为 LIS 和 LDS 长度在随机排列的情况下相互逆相关。右极大值必须从左极大值结束后开始，因此这似乎是一个安全的假设。
对于随机排列，LIS 的长度遵循Tracy-Widom 分布，因此其平均值为 sqrt(2N)，标准差为 N^(-1/6)。因此，大小的期望平方为 2N + 1/(N^1/3)，约等于 2N。这不完全是我们想要的证明，因为您需要对部分密度函数求和才能严谨地证明，但 LIS 已经是左极大值大小的上界，所以我认为结论仍然成立。
C++ 代码（Result 类和一些变量名取自 selbie 的帖子，如上所述）：
struct Result
{
    size_t i;
    size_t j;
    int64_t value;
};


Result find_best_sum_size_product(const std::vector<int>& nums)
{   
    /* Given: list of positive integers nums
       Returns: Tuple with (best_i, best_j, best_product)
       where best_i and best_j maximize the product
      (nums[i]+nums[j])*(j-i) over 0 <= i < j < n

       Runtime: O(n^2) worst case,
       O(n) average on random permutations.
    */
    
    int n = nums.size();
    
    if (n < 2)
    {
        return {0,0,INT64_MIN};
    }
    
    
    std::vector<int> left_maxima_indices;
    left_maxima_indices.push_back(0);
    
    for (int i = 1; i < n; i++){
        if (nums.at(i) > nums.at(left_maxima_indices.back())) {
            left_maxima_indices.push_back(i);
        }
    }
    
    std::vector<int> right_maxima_indices;
    right_maxima_indices.push_back(n-1);
    
    for (int i = n-1; i >= 0; i--){
        if (nums.at(i) > nums.at(right_maxima_indices.back())) {
            right_maxima_indices.push_back(i);
        }
    }
    
    size_t best_i = 0;
    size_t best_j = 0;
    int64_t best_product = INT64_MIN;
    int i = 0;
    int j = 0;

    for (size_t left_idx = 0;
         left_idx < left_maxima_indices.size();
         left_idx++)
    {
        i = left_maxima_indices.at(left_idx);

        for (size_t right_idx = 0;
            right_idx < right_maxima_indices.size();
            right_idx++)
        {   
            j = right_maxima_indices.at(right_idx);
            if (i == j) continue;
            
            int64_t value = (nums.at(i) + (int64_t)nums.at(j)) * (j - i);
            if (value > best_product)
            {
                best_product = value;
                best_i = i;
                best_j = j;
            }
        }
    }

    return { best_i, best_j, best_product };
}
2
令人印象深刻。做得好。 "且 j 右侧所有元素必须严格小于 A[j] " 的观察是我缺失的一部分。 - selbie
1
你可以简化for循环，只需这样写：for(auto i : left_maxima_indices) 和 for(auto j : right_maxima_indices)。在进行push_back循环之前，在 left_maxima_indices 上调用.reserve 可以稍微提高执行速度。对于 right_maxima_indices 向量也一样。 - selbie
1
我找到了一个关键序列。通过稍微改进您的解决方案，我能够找到这个关键序列的解决方法，但我仍然不知道它是否能解决未知的最坏情况。 - Damien
1

我从@selbie和@kcsquared的两个出色答案开始。

他们的解决方案对于随机输入给出了令人印象深刻的结果。不清楚的是最坏情况下的表现。

哪个序列会对应于最坏情况？

我终于找到了这两个答案的关键序列，即三角形序列：这个序列略微增加到最大值，然后略微减少。使用这样的序列和n = 10 ^ 5的例子，这些答案需要超过10秒。

我的解决方案从@selbie解决方案开始，并添加了两个改进：

  • 我添加了@kcsquared的技巧：在右侧（j的右侧），它们只能是较低的元素

  • 考虑新的左元素a [i]时，从i + 1开始获取第二个元素是无用的。我们可以从当前的best_j开始

通过这些技巧，我能够稍微提高两个发布的答案的性能。但是，它仍然无法解决三角形序列问题：n = 10 ^ 5时需要约10秒。

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <chrono>

struct Result {
    size_t i;
    size_t j;
    int64_t value;
};

void print (const Result& res, const std::string& prefix = "") {
    std::cout << prefix;
    std::cout << "(" << res.i << ", " << res.j << ") -> " << res.value << std::endl;
}

Result findBest(const std::vector<int>& a) {
    if (a.size() < 2) {
        return { 0, 0, INT64_MIN };
    }
    int n = a.size();  
    std::vector<int> next_max(n, -1);
    int current_max = n-1;
    for (int i = n-1; i >= 0; --i) {
        if (a[i] > a[current_max]) {
            current_max = i;
        }
        next_max[i] = current_max;
    }
    
    size_t besti = 0;
    size_t bestj = 0;
    int64_t bestvalue = INT64_MIN;
    int minimum = INT_MIN;
    
    for (size_t i = 0; i < a.size(); i++) {
        if (a[i] <= minimum) {
            continue;
        }
        minimum = a[i];
        size_t jmin = (bestj > i) ? bestj : i+1;
        for (size_t j = jmin; j < a.size(); j++) {
            j = next_max[j];
            value = (a[i] + (int64_t)a[j]) * (j - i);
            if (value > bestvalue) {
                bestvalue = value;
                besti = i;
                bestj = j;
            } 
        }
    }
    return { besti, bestj, bestvalue };
}

int main() {
    int n = 1000000;
    int vmax = 100000000;
       
    std::vector<int> A (n);
    std::srand(std::time(0));
    for (int i = 0; i < n; ++i) {
        A[i] = rand() % vmax + 1;
    }
    
    std::cout << "n = " << n << std::endl;
    auto t0 = std::chrono::high_resolution_clock::now();
    auto res = findBest (A);
    auto t1 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
    print (res, "Random: ");
    std::cout << "time = " << duration/1000 << " ms" << std::endl;
    
    int i_max = n/2;
    for (int i = 0; i < i_max; ++i) A[i] = i+1;
    A[i_max] = 10 * i_max;
    for (int i = i_max+1; i < n; ++i) {
        A[i] = 2*i_max - i;
    }
    t0 = std::chrono::high_resolution_clock::now();
    res = findBest (A);
    t1 = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
    print (res, "Triangle sequence: ");
    std::cout << "time = " << duration/1000 << " ms" << std::endl;
    
    return 0;
}
只是想澄清一下，这个解决方案是否适用于一般序列，还是只适用于“三角形”序列？这些想法可能会扩展到整个问题的次二次最坏情况解决方案！顺便说一句，我认为更常见的术语是单峰函数/序列，以及“强”或“严格”的单峰性，但我还没有找到关于通常术语的明确答案。 - kcsquared
这对于 [9, 65, 88, 18, 6] 给出了错误的答案，正确答案应该是 213。我不确定语句 当考虑一个新的左元素 a[i] 时，从 i + 1 开始获取第二个元素是无用的。我们可以从当前的 best_j 开始。 是否正确；你知道一个证明吗？ - kcsquared
1
@kcsqured 我进行了许多随机序列的测试，结果总是和你的一样。我没有正式的证明，但我会检查这个特定的序列。 - Damien
经过进一步的测试，您的方法似乎确实有效：我们可以从best_j开始。我仍然不确定如何证明它或它对时间界限有什么影响，但这是一个非常显著的事实。 - kcsquared
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接