Hi,

This question was asked in one of online coding test on hackerEarth.
Although, I have contributed this question to leetcode, but it is still in pending state, hence asking in discuss section.

You are given an array A of the size 3N. You have to split the array into N triplets such that the sum of all the triplets' score is maximized Score of a triplet (x, y, z) is the second element in the triplet after it has been sorted.

Example:

N=2

nums = [1,2,3,4,5,6]
output= 8 ( first triplet score of (1,3,4) = 3 + score(2,5,6) = 5 )

ans = 10

P.S:
One of the possible solution I can think of is greedy one.But I am not sure how to proof correctness of greedy solution.
Basically, sort the array. and start with second last element.
then reduce the index by 2 till all the elements are picked.
Skipped element could be start/end of some triplet.
This solution did not work. it passed only 2 test cases.

TIA