Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Observations
3.
Implementation Idea
3.1.
Brute Force
3.2.
Better Approach
4.
Algorithm
5.
Code
6.
Frequently Asked Questions
6.1.
What is considered a balanced tree?
6.2.
What is a balanced tree to give an example?
6.3.
What is the difference between subsequence and subarray?
6.4.
What is the difference between subset and subsequence?
7.
Conclusion
Last Updated: Mar 27, 2024

Find the Increasing subsequence of length three with maximum product

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction 

Let’s understand the problem statement first, we are given an array and we want to find three numbers in the array in increasing order as a subsequence which gives us the maximum product.

Here you can understand 

Input  :1,2,3,4,5,6,7,8

Output : 6*7*8

Input  : 4,5,1,2,8, 3, 11,9

Output : 5*8*11

Observations

Product is maximum when numbers you are multiplying are large. So our goal should be to maximise the numbers we are multiplying, but with two constraints.
A. Numbers should be subsequences of arrays.
B. They should be in increasing order.  

So for each number if I find the largest number smaller than this number in the array left to it, And the largest number greater than it in the array right to it, and take max of all of them then we are done. 

Now we have to find some way by which we can find the above values for each number. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!!

Previous article
Maximum Width of a Binary Tree
Next article
Find the Sum of nodes at maximum depth of a Binary Tree
Live masterclass