如何在具有最大乘积的数字数组中找到一个三元组？

Question

今天卡在下面problem.Kindly提供一些线索，声明如下：

给定一个大小为 n 的数组 A[]。在以下约束条件下最大化 A[i]*A[j]*A[k]：

我 < j < k
A[i] < A[j] < A[k]

我试过的代码如下：

#include<iostream>
using namespace std;

int main(){
  int A[]={1,3,6,8,9};
  int max=0;
  int n=sizeof(A)/sizeof(A[0]);
  for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
        for(int k=j+1;k<n;k++)
        {
          if(A[i]<A[j]&&A[j]<A[k]&&max<A[i]*A[j]*A[k])
            max=A[i]*A[j]*A[k];
        }
        cout<<max;
   return 0;
}

Answer 1

给定 i < j < k 并且你想用 3 个 for 循环做某事，那么你显然可以做到

for(i = 0; i < n; ++i) {
    for(j = i + 1; j < n; ++j){
         if (A[i] < A[j]) {
             for(k = j + 1; k < n; ++k){
                 if(A[j] < A[k]) {
                 /*DoSomething with i,j,k*/
                 }
            }
         }
    }
}

这主要是缩进的噩梦。

Answer 2

下面的解应该是O(n^2)

#include <stack>
#include <iostream>
#include <stdexcept>

template <typename T>
std::stack<T> getStack (T const * a, std::size_t dimA)
 {
   if ( nullptr == a )
      throw std::runtime_error("nullptr in getStack()");

   if ( 0U == dimA )
      throw std::runtime_error("no values in getStack()");

   T              top;
   std::stack<T>  s;
   std::size_t    pos{ 0U };

   s.push(top = a[pos]);

   do
    {
      if ( top < a[pos] )
         s.push(top = a[pos]);
    }
   while ( ++pos < dimA );

   return s;
 }


int main()
 {
   int          a[] { 34, 12, 3, 7, 29, 45 };
   std::size_t  dimA { sizeof(a)/sizeof(a[0]) };
   std::size_t  numMult { 3U };


   std::stack<int> s;

   std::size_t     pos { 0U };

   do
    {
      s = getStack(a+pos, dimA - pos);
    }
   while ( (s.size() < numMult) && (numMult <= (dimA - ++pos)) );

   if ( s.size() < numMult )
      std::cout << "there is no solution" << std::endl;
   else
    {
      int res { s.top() };

      for ( auto ui = 1U ; ui < numMult ; ++ui )
       {
         s.pop();

         res *= s.top(); 
       }

      std::cout << "the solution is " << res << std::endl;
    }

   return 0;
 }

Answer 3

有一个简单的 O(N^2) 算法。这是大纲：

对于每个元素y
搜索小于y且在y

x

搜索大于y且在y

z

步骤 1 是 O(N)，步骤 2 和 3 可以在同一个循环中完成，即 O(N)，总共是 O(N^2)

也有一个O(N lg N)的算法，但是比较复杂：

我们可以在 O(N) 中预先计算并在 O(1) 中查询以找到范围 [l,r] 中的最大值。 （最初的想法是使用线段树或任何RMQ结构，感谢@PetarPetrovic指出）

我们还在迭代数组中的每个元素时动态构建一个集合（排序列表）。伪代码如下：

Array A = []
Set S = {}
Ans = 0

For i = 0 to N // O(N)
  // A[i] is y
  x = binary search S, maximum element in S which is < A[i] //O(lg N)
  z = RMQ(i+1, N) // O(lg N), or O(1) if we precompute in O(N)
  if(x < A[i] && A[i] < z) Ans = Max(Ans, x*A[i]*z)
  Insert A[i] into S // O(lg N)
//Total is O(N lg N)

我们尝试将A[i]视为中间元素y。

由于我们有一个包含 i 之前所有元素的有序集合，我们可以使用该集合对最大有效 x 进行二进制搜索。之后我们将当前元素插入到这个集合中。

我们使用 O(N) 预先计算数组并在 O(1) 中查询以找到范围 [i+1, N-1] 中的最大值。找到的数字是 z.

如果 (x,y,z) 是有效元组且大于当前答案，我们更新答案。

如何在具有最大乘积的数字数组中找到一个三元组？

How to find the a triplet in an array of numbers having maximum product?

algorithm

complexity-theory

maximize