Given a sequence of non-negative integers, find the subsequence of length 3 having maximum product, with the elements of the subsequence being in increasing order.
 
Example 1:
Ã¢â¬â¹Input:
n = 8
arr[ ] = {6, 7, 8, 1, 2, 3, 9, 10}
Output:
8 9 10
Explanation: 3 increasing elements of 
the given arrays are 8,9 and 10 which 
forms the subsequence of size 3 with 
maximum product.
Ã¢â¬â¹Example 2:
Input:
n = 4
arr[ ] = {3, 4, 2, 1} 
Output:
Not Present 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maxProductSubsequence() that takes an array arr, sizeOfArray n, and return the subsequence of size 3 having the maximum product, numbers of subsequence being in increasing order. If no such sequence exists, return "-1". The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{5}
1 <= Arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def countArray (self, arr, n) : 
        #Complete the function


Solutions:
from bisect import bisect_left

def BinarySearch(a, x):
	i = bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def findMaximumBefore(arr, n):
	res = [-1] * (n + 1)
	lst = []
	lst.append(arr[0])
	for i in range(1, n):
		idx = BinarySearch(lst, arr[i])
		if idx != -1:
			res[i] = lst[idx]
		lst.insert(idx + 1, arr[i])
	return res

class Solution:

	def countArray(self, arr, n):
		small = findMaximumBefore(arr, n)
		large = [0] * n
		large[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			large[i] = max(large[i + 1], arr[i])
		res = -1
		ans = [-1]
		for i in range(1, n - 1):
			if small[i] != -1 and large[i + 1] > arr[i]:
				if res < small[i] * arr[i] * large[i + 1]:
					res = small[i] * arr[i] * large[i + 1]
					ans = [small[i], arr[i], large[i + 1]]
		return ans


import bisect
import sys

class Solution:

	def countArray(self, arr, n):
		g = [-1] * n
		maxi = arr[-1]
		for i in range(n - 2, -1, -1):
			g[i] = max(maxi, arr[i])
			maxi = g[i]
		s = [arr[0]]
		re = -sys.maxsize
		l = [-1]
		for i in range(1, n - 1):
			x = bisect.bisect_left(s, arr[i])
			if x != 0 and g[i] > arr[i] and (arr[i] * g[i] * s[x - 1] > re):
				re = arr[i] * g[i] * s[x - 1]
				l = [s[x - 1], arr[i], g[i]]
			bisect.insort(s, arr[i])
		return l


import bisect as bs

class Solution:

	def countArray(self, arr, n):
		greatest = [-1] * n
		greatest[-1] = arr[-1]
		for i in range(n - 2, -1, -1):
			greatest[i] = max(arr[i], greatest[i + 1])
		less = [arr[0]]
		maxx = float('-inf')
		for i in range(1, n - 1):
			z = bs.bisect_left(less, arr[i])
			if z != 0 and greatest[i + 1] > arr[i] and (maxx < less[z - 1] * arr[i] * greatest[i + 1]):
				maxx = less[z - 1] * arr[i] * greatest[i + 1]
				ans = [less[z - 1], arr[i], greatest[i + 1]]
			bs.insort(less, arr[i])
		if maxx == float('-inf'):
			return [-1]
		return ans


class Solution:

	def binPartition(self, a, value):
		from bisect import bisect_left as bl
		return bl(a, value) - 1

	def countArray(self, a, n):
		if n < 3:
			return [-1]
		left = [-1, a[0]]
		result = [-1]
		right = max(a[1:])
		maxproduct = -1
		for i in range(1, n - 1):
			current = a[i]
			if current >= right:
				right = max(a[i + 1:])
			j = self.binPartition(left, current)
			leftValue = left[j]
			left.insert(j + 1, current)
			rightValue = right
			if not (leftValue < current and current < rightValue):
				continue
			currentprod = leftValue * rightValue * current
			if currentprod > maxproduct:
				maxproduct = currentprod
				result = [leftValue, current, rightValue]
		return result


from bisect import bisect_left

class Solution:

	def countArray(self, arr, n):
		if n < 3:
			return -1
		maxRight = [0] * n
		maxRight[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			maxRight[i] = max(arr[i], maxRight[i + 1])
		maxProduct = -1
		minLeft = arr[0]
		lst = [arr[0]]
		for i in range(1, n - 1):
			indexLargestSmaller = bisect_left(lst, arr[i])
			if indexLargestSmaller and arr[i] < maxRight[i + 1]:
				if lst[indexLargestSmaller - 1] * arr[i] * maxRight[i + 1] > maxProduct:
					(a, b, c) = (lst[indexLargestSmaller - 1], arr[i], maxRight[i + 1])
					maxProduct = a * b * c
			lst.insert(indexLargestSmaller, arr[i])
		return [-1] if maxProduct == -1 else (a, b, c)


from bisect import bisect_left

class Solution:

	def countArray(self, arr, n):
		stck = [arr[0]]
		prev = [-1]
		for i in range(1, n):
			ind = bisect_left(stck, arr[i])
			if ind == 0:
				prev.append(-1)
			else:
				prev.append(stck[ind - 1])
			stck.insert(ind, arr[i])
		maximum = arr[n - 1]
		front = [-1]
		for i in range(n - 2, -1, -1):
			if arr[i] >= maximum:
				front.append(-1)
				maximum = arr[i]
			else:
				front.append(maximum)
		front = front[::-1]
		ans = []
		pro = 0
		for i in range(n):
			a = [prev[i], arr[i], front[i]]
			p = a[0] * a[1] * a[2]
			if p > pro:
				ans = a.copy()
				pro = p
		return ans


class Solution:

	def binPartition(self, a, value):
		right = len(a) - 1
		left = 0
		while True:
			mid = (left + right) // 2
			if value == a[mid]:
				return mid - 1
			if value < a[mid]:
				right = mid - 1
			else:
				left = mid + 1
			if left > right:
				if a[mid] < value:
					return mid
				return mid - 1

	def countArray(self, a, n):
		if n < 3:
			return [-1]
		left = [-1, a[0]]
		result = [-1]
		right = max(a[1:])
		maxproduct = -1
		for i in range(1, n - 1):
			current = a[i]
			if current >= right:
				right = max(a[i + 1:])
			j = self.binPartition(left, current)
			leftValue = left[j]
			left.insert(j + 1, current)
			rightValue = right
			if not (leftValue < current and current < rightValue):
				continue
			currentprod = leftValue * rightValue * current
			if currentprod > maxproduct:
				maxproduct = currentprod
				result = [leftValue, current, rightValue]
		return result


from bisect import bisect_left as bl

class Solution:

	def countArray(self, arr, n):
		if n < 3:
			return [-1]
		left = [arr[0]]
		res = [-1]
		right = max(arr[1:])
		maxproduct = -1
		for i in range(1, n - 1):
			temp = arr[i]
			if temp >= right:
				right = max(arr[i + 1:])
			j = bl(left, temp)
			lv = left[j - 1]
			left.insert(j, temp)
			rv = right
			if not (temp < rv and temp > lv):
				continue
			currpro = lv * temp * rv
			if currpro > maxproduct:
				maxproduct = currpro
				res = [lv, temp, rv]
		return res


from collections import deque
from bisect import bisect_left as bl

class Solution:

	def countArray(self, a, n):
		if n < 3:
			return [-1]
		res = [-1]
		max_prod = -1
		left = [arr[0]]
		right = arr[1:]
		leftVal = arr[0]
		rightVal = max(right)
		for i in range(1, n - 1):
			val = arr[i]
			j = bl(left, val)
			if val >= rightVal:
				rightVal = max(arr[i + 1:])
			left.insert(j, val)
			leftVal = left[j - 1]
			if leftVal < val and val < rightVal:
				product = leftVal * val * rightVal
				if product > max_prod:
					max_prod = product
					res = (leftVal, val, rightVal)
		return res


from bisect import bisect_left

class Solution:

	def countArray(self, arr, n):
		if n < 3:
			return [-1]
		left = [-1, arr[0]]
		res = [-1]
		right = max(arr[1:])
		product = -1
		for i in range(1, n - 1):
			curr = arr[i]
			if curr >= right:
				right = max(arr[i + 1:])
			j = bisect_left(left, curr) - 1
			leftVal = left[j]
			left.insert(j + 1, curr)
			rightVal = right
			if not leftVal < curr < rightVal:
				continue
			currProd = leftVal * curr * right
			if currProd > product:
				product = currProd
				res = [leftVal, curr, rightVal]
		return res


import sys
import bisect

class Solution:

	def countArray(self, arr, n):
		if n < 3:
			return -1
		answer = [-1, -1, -1]
		smaller = [-1] * n
		elements = []
		for i in range(n):
			index = bisect.bisect_left(elements, arr[i])
			bisect.insort(elements, arr[i])
			if index != 0:
				smaller[i] = elements[index - 1]
		product = -sys.maxsize
		maxRight = arr[-1]
		for i in range(n - 2, 0, -1):
			if arr[i] >= maxRight:
				maxRight = arr[i]
			elif smaller[i] != -1:
				temp = smaller[i] * arr[i] * maxRight
				if temp > product:
					product = temp
					answer[0] = smaller[i]
					answer[1] = arr[i]
					answer[2] = maxRight
		return answer


from bisect import bisect_left

class Solution:

	def BinarySearch(self, a, x):
		i = bisect_left(a, x)
		if i:
			return i - 1
		else:
			return -1

	def countArray(self, arr, n):
		LGR = [i for i in arr]
		LGR[-1] = -1
		max_from_right = arr[n - 1]
		for i in range(n - 2, -1, -1):
			temp = LGR[i]
			LGR[i] = max_from_right
			if max_from_right < temp:
				max_from_right = temp
		LSL = [0] * n
		LSL[0] = -1
		lst = []
		lst.append(arr[0])
		for i in range(1, n):
			idx = self.BinarySearch(lst, arr[i])
			if idx != -1:
				LSL[i] = lst[idx]
			lst.insert(idx + 1, arr[i])
		maxProduct = float('-inf')
		ans = [-1]
		for i in range(0, n):
			currP = LSL[i] * arr[i] * LGR[i]
			if currP > maxProduct and LSL[i] < arr[i] and (arr[i] < LGR[i]):
				ans = []
				ans.extend([LSL[i], arr[i], LGR[i]])
				maxProduct = currP
		return ans


import bisect

class Solution:

	def countArray(self, arr, n):
		max_from_right = [0] * n
		smaller = [-1] * n
		elems = [arr[0]]
		for i in range(1, len(arr)):
			pos = bisect.bisect_left(elems, arr[i])
			if pos == len(elems):
				elems.append(arr[i])
			elif elems[pos] != arr[i]:
				elems.insert(pos, arr[i])
			if pos == 0:
				smaller[i] = -1
			else:
				smaller[i] = elems[pos - 1]
		maxi = -1
		for i in range(n - 1, -1, -1):
			maxi = max(arr[i], maxi)
			max_from_right[i] = maxi
		result = 0
		output = [0, 0, 0]
		for i in range(0, len(arr) - 1):
			if smaller[i] != -1 and smaller[i] < arr[i] and (arr[i] < max_from_right[i]):
				temp = smaller[i] * arr[i] * max_from_right[i]
				if temp > result:
					result = temp
					output = [smaller[i], arr[i], max_from_right[i]]
		if result == 0:
			return ['Not', 'Present']
		return output


import bisect

class Solution:

	def countArray(self, arr, n):
		max_from_right = [0] * n
		smaller = [-1] * n
		elems = []
		bisect.insort(elems, arr[0])
		for i in range(1, len(arr)):
			bisect.insort(elems, arr[i])
			pos = bisect.bisect_right(elems, arr[i] - 1)
			if pos == 0:
				smaller[i] = -1
			else:
				smaller[i] = elems[pos - 1]
		maxi = -1
		for i in range(n - 1, -1, -1):
			maxi = max(arr[i], maxi)
			max_from_right[i] = maxi
		result = 0
		output = [0, 0, 0]
		for i in range(0, len(arr) - 1):
			if smaller[i] != -1 and smaller[i] < arr[i] and (arr[i] < max_from_right[i]):
				temp = smaller[i] * arr[i] * max_from_right[i]
				if temp > result:
					result = temp
					output = [smaller[i], arr[i], max_from_right[i]]
		if result == 0:
			return ['Not', 'Present']
		return output


import bisect

class Solution:

	def countArray(self, arr, n):
		l = [arr[0]]
		small = [-1]
		for i in range(1, n):
			ind = bisect.bisect_left(l, arr[i])
			if ind == 0:
				small.append(-1)
			else:
				small.append(l[ind - 1])
			bisect.insort(l, arr[i])
		large = arr.copy()
		for i in range(n - 2, -1, -1):
			large[i] = max(large[i], large[i + 1])
		ans = []
		prod = float('-inf')
		for i in range(1, n - 1):
			if small[i] == -1 or arr[i] >= large[i]:
				continue
			else:
				p = small[i] * arr[i] * large[i]
				if p > prod:
					prod = p
					ans = [small[i], arr[i], large[i]]
		return ans if ans else [-1]


from bisect import bisect_left

class Solution:

	def countArray(self, arr, n):
		large = [arr[-1]] * n
		for i in range(n - 2, 1, -1):
			large[i] = max(arr[i], large[i + 1])
		sarr = []
		maximum = 0
		ans = None
		for i in range(1, n - 1):
			j = bisect_left(sarr, arr[i])
			sarr.insert(j, arr[i])
			if j > 0 and large[i + 1] > arr[i]:
				product = sarr[j - 1] * arr[i] * large[i + 1]
				if product > maximum:
					maximum = product
					ans = [sarr[j - 1], arr[i], large[i + 1]]
		return ans if ans else [-1]


import bisect

class Solution:

	def countArray(self, a, n):
		(s, ans, res) = ([], 0, [-1])
		b = a.copy()
		for i in range(n - 2, -1, -1):
			b[i] = max(b[i], b[i + 1])
		for i in range(1, n - 1):
			bisect.insort(s, a[i])
			p = bisect.bisect_left(s, a[i])
			if p != 0 and a[i] < b[i + 1]:
				p -= 1
				if s[p] * a[i] * b[i + 1] > ans:
					ans = s[p] * a[i] * b[i + 1]
					res = [s[p], a[i], b[i + 1]]
		return res


from heapq import heappush, heappop

class Solution:

	def countArray(self, a, n):
		(ans, best) = ([-1], -1)
		(m, q) = ([0] * (n + 1), [])
		for i in range(n - 1, -1, -1):
			m[i] = max(a[i], m[i + 1])
		for (i, x) in enumerate(a):
			while q and q[0] < x and (x < m[i + 1]):
				t = q[0] * x * m[i + 1]
				if t > best:
					best = t
					ans = [q[0], x, m[i + 1]]
				heappop(q)
			heappush(q, x)
		return ans


class Solution:

	def isValid_lis(self, a, n):
		if len(a) != n:
			return False
		for i in range(1, n):
			if a[i] <= a[i - 1]:
				return False
		return True

	def cal_max(self, lis1, lis2, n):
		if self.isValid_lis(lis1, n) == False or self.isValid_lis(lis2, n) == False:
			if self.isValid_lis(lis1, n):
				return lis1
			if self.isValid_lis(lis2, n):
				return lis2
			return []
		p1 = 1
		p2 = 1
		for i in range(n):
			p1 = p1 * lis1[i]
			p2 = p2 * lis2[i]
		if p1 > p2:
			return lis1
		return lis2

	def countArray(self, a, n):
		tops = [[], [], []]
		for i in range(n - 1, -1, -1):
			tops[0] = list(self.cal_max(tops[0], [a[i]], 1))
			if tops[1]:
				temp = list(tops[1])
				temp[0] = a[i]
				tops[1] = list(self.cal_max(tops[1], temp, 2))
			temp = [a[i]] + tops[0]
			tops[1] = list(self.cal_max(tops[1], temp, 2))
			if tops[2]:
				temp = list(tops[2])
				temp[0] = a[i]
				tops[2] = list(self.cal_max(tops[2], temp, 3))
			temp = [a[i]] + tops[1]
			tops[2] = list(self.cal_max(tops[2], temp, 3))
		if tops[2]:
			return tops[2]
		return [-1]


from bisect import bisect_left, insort
from functools import reduce

class Solution:

	def countArray(self, arr, n):
		prod = lambda l: reduce(lambda x, y: x * y, l)
		rmax = [0] * n
		rmax[-1] = arr[-1]
		for i in range(n - 2, -1, -1):
			rmax[i] = max(rmax[i + 1], arr[i])
		sorted_arr = [arr[0]]
		res = [-1, -1, -1]
		for i in range(1, n - 1):
			if rmax[i + 1] > arr[i]:
				j = bisect_left(sorted_arr, arr[i]) - 1
				if j and prod([sorted_arr[j], arr[i], rmax[i + 1]]) > prod(res):
					res = (sorted_arr[j], arr[i], rmax[i + 1])
			insort(sorted_arr, arr[i])
		return res