1.

Find the subsequence of length 3 with the highest product from a sequence of non-negative integers, with the elements in increasing order.

Answer»


  • Input: n = 8 arr[ ] = {6, 7, 10, 1, 2, 3, 11, 12}


  • Output: {10, 11, 12}

The three increasing elements of the given arrays are 10, 11, and 12, which form a three-size subsequence with the highest product.

vector<int> maxProductSubsequence(int *a , int n)
{
set<int> s;
long long largestOnLeft[n];
for(int i=0;i<n;i++)
{
s.insert(a[i]);
auto it=s.lower_bound(a[i]);
if(it==s.begin())
{
largestOnLeft[i]=-1;
continue;
}
it--;
largestOnLeft[i]=*it;
}
int m=0;
long long p=INT_MIN;
vector<int> result(3);
result[0]=-1;
for(int i=n-1;i>=0;i--)
{
if(a[i]>=m){
m=a[i];}
else
{
if(largestOnLeft[i] !=-1)
{
if(largestOnLeft[i]*a[i]*m >p)
{
p=largestOnLeft[i]*a[i]*m;
result[0]=largestOnLeft[i];
result[1]=a[i];
result[2]=m;
}
}
}
}
return v;
}


  • Time Complexity: O(nlog(n))


  • Space Complexity: O(n)


Discussion

No Comment Found

Related InterviewSolutions