NCR problem

help
1

You are given an array
You have to find max(A[i]+(A[j]*A[k])

such that
i<j<k
and
A[i]<A[j]<A[k]

Problem was asked in NCR Campus Codewars

Pls help…

@anon55659401
@guitarlover
@ssrivastava990

3 Likes
3

you can’t sort the array when you have to maintain the order of index.

4

you need to find for every index and then print it. in simple words for every i divide the array in two parts now find the max a[i] in left part and max and second maximum in Right part.
but obviously you can’t apply multiple loops.
can you think of solution now.
hint: make a array maximum [i] which store the maximum value from 0to i.

5

also, if you are sorting then why do you need greedy. just take the last 3 elements.

6

@sahai_harshit Can be done using the BIT .
See this code for more explanation code
Revert back to me if not getting something.

7

make two multisets. name it prefix and suffix. first insert all the elements from index 1in the suffix multiset. start traversing the array from index 1 to index n-2(i assume n is size of array). now at each index , do three things .

  1. delete the current element from the suffix multiset.
  2. insert previous element in the prefix multiset.
  3. maximum value possible for current index is the largest element in the prefix array + current element *largest element in the suffix array.
    Take maximum of all values.
    Time Complexity - O(nlogn)
    Hope , it helps.
1 Like
8

can u please explain by taking some example , it will be more helpful.

9

i am fixing the index j and finding best i and k for it respectively.
lets assume we are at index j.
so the prefix multiset will have all elements from 0 to j-1.(provides best i such that i<j).
suffix multiset will have all elements from j+1 to n-1.(provides best k such that k>j).
so max value for index j will be max element from prefix multiset + current element * max element from suffix multiset.
let the array be [5,2,4,1,3]
assume we are at index 2.(array is 0 indexed)
prefix multiset is [2,5].
suffix multiset is [1,3].
so max value for index 2 is 5 + 4*3 .
answer is maximum of all these values obtained from each index.

1 Like
10

Condition is
i<j<k
as well as
A[i]<A[j]<A[k]

@pd_nik

11

Here is my approach

  • Sort the array in descending order along with indexes

  • Find the nearest triplet such that i<j<k . Thats the answer because we sorted the array in descending order .

  • If there is no triplet such that i<j<k . Then consider the first 3 maximum values of the array in the answer

12

I have done it using TreeSet and Suffix Array.
O(nlogn).

13

oh sorry. my bad. i didn’t read the problem carefully.
this problem can be done with the approach i suggested.
now instead of finding the largest element from the prefix multiset, we will find the largest element less than the current element . this can be done using lowerbound and decreasing the iterator in the prefix multiset.
anf for suffix multiset , we need to find the largest element which should be greater than the current elemnt.
for this we just need to check if *suffix.rbegin()>current elemnt.
and then take the maximum of all values.

1 Like
14

Can u walk me through the example
@pd_nik

15

What is querying function querying for ??
@nehra_1997

16

condition :-
1.i<j<k
2. a[i] < a[j] < a[k]
array = [5,1,4,2,7]
i=1;
suffix multiset=[2,4,7],prefix multiset=[5]
verdict - since there is no element in the prefix multiset which is less than 1, so we can’t fix j and satisfy the condition 2.
i=2;
suffix multiset=[2,7],prefix multiset=[1,5]
verdict -largest element in the prefix multiset less than 4 is 1 and largest element in the suffix multiset is 7 which is greater than 4 , therefore we get a value here.
which is 1+47=29
i=3;
suffix multiset=[7],prefix multiset=[1,4,5]
verdict -largest element in the prefix multiset less than 2 is 1 and largest element in the suffix multiset is 7 which is greater than 2 , therefore we get a value here.
which is 1+27=15
since the answer is maximum of the values obtained , therefore the answer is 29.
for this array.

1 Like
17

Each time the query function will return the max value of A[i]+(A[j]*A[k] found so far …!!!
If not getting plz dry run the code ,u will get more …!!!

18

Thanks to all for ur approaches

19

You can solve it easily using convex hull trick.

We can maintain a line for each j, which has slope a[j] and intercept a[i] such that i<j and a[i] < a[j] and a[i] is max out of all such i. T

Now we can iterate over k. The answer is simply the max of all the lines we have so far, at x=a[k]. After this, we also need to add the line corresponding to k. For that we need the intercept as described above. We can use a segment tree to find out the suitable a[i].

Complexity O(n \log n)

20

I think you need to check if the current element is negative or not and then decide whether to choose the smallest from the suffix array(in case the current element is -ve) or choose the greatest(if the current element is +ve). Rest is fine.

21

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)