Find the Increasing subsequence of length three with maximum product | GeeksforGeeks

Find the Increasing subsequence of length three with maximum product Given a sequence of non-negative integers, find the subsequence of length 3 having maximum product with the numbers of the subsequence being in ascending order. 

Since we want to find the maximum product, we need to find following two things for every element in the given sequence:
LSL: The largest smaller element on left of given element
LGR: The largest greater element on right of given element.

Once we find LSL and LGR for an element, we can find the product of element with its LSL and LGR (if they both exist). We calculate this product for every element and return maximum of all products.

We can do this in O(nLogn) time. For simplicity, let us first create two arrays LSL[] and LGR[] of size n each. The main task is to fill two arrays LSL[] and LGR[].

We can fill LSL[] in O(nLogn) time. The idea is to use a Balanced Binary Search Tree like AVL. We start with empty AVL tree, insert the leftmost element in it. Then we traverse the input array starting from the second element to second last element. For every element currently being traversed, we find the floor of it in AVL tree. If floor exists, we store the floor in LSL[], otherwise we store NIL. After storing the floor, we insert the current element in the AVL tree.

We can fill LGR[] in O(n) time. The idea is similar to this post. We traverse from right side and keep track of the largest element. If the largest element is greater than current element, we store it in LGR[], otherwise we store NIL.

Finally, we run a O(n) loop and return maximum of LSL[i]*arr[i]*LGR[i]

Code: http://ideone.com/ul6Ypo
http://ideone.com/m10rOg Not sure

1. int getMaxProduct(int *arr, int n)
2. {
3. if(n < 3) return 0;
4. //First calculate the max value that is larger than the current value in the right of each element
5. calculateRightMax(arr, n);
6. //Secondly calculate the max value that is smaller than the current value in the left of each element
7. calculateLeftMax(arr, n);
8. //Now get maximum of product
9. int maxProduct = 0, curProduct = 0;
10. for(int i = 1; i < n - 1; ++i)
11. {
12. curProduct = leftMaxArr[i] * arr[i] * rightMaxArr[i];
13. if(curProduct > maxProduct)
14. maxProduct = curProduct;
15. }
16. return maxProduct;
17. }
18. int *rightMaxArr;
19. int *leftMaxArr;
20. void calculateRightMax(int * arr, int n)
21. {
22. int maxVal = 0;
23. for(int i = n - 1; i >= 0; --i)
24. {
25. if(maxVal > arr[i])
26. rightMaxArr[i] = maxVal;
27. else
28. maxVal = arr[i];
29. }
30. }
31. void calculateLeftMax(int * arr, int n)
32. {
33. stack<int> stackA;
34. stackA.push(arr[0]);
35. int curPos = 1, leftMax = 0;
36. while(curPos < n)
37. {
38. if(rightMaxArr[curPos] == 0)
39. {
40. ++curPos;
41. continue;
42. }
43.  
44. leftMax = 0;
45. while(!stackA.empty() && arr[curPos] >= stackA.top())
46. {
47. if(arr[curPos] > stackA.top())
48. leftMax = stackA.top();
49. stackA.pop();
50. }
51.  
52. leftMaxArr[curPos] = leftMax;
53. stackA.push(arr[curPos++]);
54. }
55. }

a simple solution of (nlog(n))... correct me if i am wrong. 
Sorting the array along with arranging their indices in some other array..
for eg . if array is 5 10 8 9
then sorting gives 5 8 9 10 and indices array turn into 0 2 3 1... 
now we select 3 strictly decreasing indices from the end..

Read full article from Find the Increasing subsequence of length three with maximum product | GeeksforGeeks