Find the Increasing subsequence of length three with maximum product

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)

You can also try this code with Online Python Compiler

Run Code

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!!