## Implementation Idea

### Brute Force

For each element find the largest element smaller than the current element by just going to left of this element in the array. And similarly for the right too to find the largest element larger than this element. As for each element we are iterating the array, the time complexity will be O(n^2).

Letâ€™s see if we can lower this by use of some data structure. If we have read data structures we will understand that a balanced tree can help in this. If we traverse the array from left to right, we can just put the element in the tree and the number which is to the left of our given element is the largest element smaller than this element.

### Better Approach

For the greatest element on the right side greater than this current element, we just need to maintain a max variable which stores the maximum variable till now and if itâ€™s greater than the current element we store it for the current element if not just save -1.

For storing these values we can keep two arrays.

As in the tree the find operation is only Log(n), hence the overall time complexity will be nlog(n).

## Algorithm

- Initialise 2 arrays: LSCL[n] and LGCR[n]

LSCL: Largest element smaller than current element on left.

LGCR: Largest element greater than current element on right.

- Populate LSCL with the help of a balanced tree, and populate LGCR just by traversing from right to left and keeping track of max.
- For each element multiply arr[i] * LSCL[i] * GGCR[i] and keep the max of all such products and return this.

## Code

```
from bisect import bisect_left
def BinarySearch(a, x):
i = bisect_left(a, x)
if i:
return (i-1)
else:
return -1
def countArray(arr, n) :
# Calculate LGR for each element
LGCR=[i for i in arr]
LGCR[-1]=-1
max_from_right = arr[n-1]
for i in range(n-2,-1,-1):
temp=LGR[i]
LGCR[i]=max_from_right
if max_from_right< temp:
max_from_right=temp
# Calculate LSL for each element
LSCL = [0] * (n)
LSCL[0] = -1
lst = []
lst.append(arr[0])
for i in range(1, n):
idx = BinarySearch(lst, arr[i])
if(idx != -1):
LSCL[i] = lst[idx]
lst.insert(idx+1 , arr[i])
maxProduct=float('-inf')
ans=[-1]
for i in range(0,n):
currP = LSCL[i]*arr[i]*LGCR[i]
if currP>maxProduct and LSCL[i]<arr[i] and arr[i]<LGCR[i]:
ans=[]
ans.extend([LSCL[i],arr[i],LGCR[i]])
maxProduct=currP
return ans
ans = countArray([6, 7, 8, 1, 2, 3, 9, 10],8)
if(ans[0]==-1):
print("Not Present")
else:
print(ans)
```

## Frequently Asked Questions

#### What is considered a balanced tree?

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

#### What is a balanced tree to give an example?

The right tree is balanced, in case, for every node, the difference between its children's height is at most 1. An example of a balanced BST is a Red-Black-Tree. The Red-Black-Tree is self-balancing. Balanced BSTs are also implemented in several Java Collections

#### What is the difference between subsequence and subarray?

A subarray or substring will always be contiguous, but a subsequence need not be contiguous. That is, subsequences are not required to occupy consecutive positions within the original sequences. But we can say that both contiguous subsequence and subarray are the same.

#### What is the difference between subset and subsequence?

A subsequence maintains the relative ordering of elements but may or may not be a contiguous part of an array. For a sequence of size n, we can have 2^n-1 non-empty sub-sequences in total. A subset does not maintain the relative ordering of elements and is neither a contiguous part of an array.

## Conclusion

So in this article, we learned how we can find the Increasing subsequence of length three with maximum product, with the help of brute force approach in O(n^2) and O(nlogn) with trees.

Check out this problem - __Subarray With 0 Sum__

Check out our __Coding Ninjas Studio__ __Guided Path__ to learn about __Data Structures and Algorithms__, __Competitive Programming__, __JavaScript__, __System Design__, and more, Take a look at the mock __test series__ and participate in the __contests__ hosted by Coding Ninjas Studio if you want to improve your coding skills. If you are new to preparation and want to work for firms such as Amazon, Microsoft, Uber, and others, you should review the __problems__, __interview experiences,__ and __interview bundle__ for placement preparations.

Consider taking one of our paid __courses __to give yourself and your profession an edge!

Please vote for our blogs if you find them valuable and exciting.

Happy Learning!!