In request of repeated queries regarding my approach to MARRAYS in my solution and editorial, i am explaining my approach to MARRAYS in this post. (I hope moderators don’t mind this)
So here it goes.
First think of only first subtask in which N = 2
So, the simplest solution to this approach would be the minimum of
- Abs(Max of 1st array - Min of 2nd array)
- Abs(Min of 1st array - Max of 2nd array)
This works because only the minimum of one array and maximum of other can give the maximum absolute value. You may see this solution for 20 points (just to check this fact 
)
Now, coming to the main problem, i have basically run a brute force algorithm, discarded useless entries before processing them at next step, in short.
Coming to details, i will be making continuous reference to solution, so I’ll recommend u open this solution in next tab for better understanding.
I am solving the problem from right to left, processing (n-1) th … 2nd 1st. Left to right order is also possible and makes no difference except minor implementation changes.
Firstly i use a LinkedHashMap array, ith map storing the best results for fixed first value of ith array.
That is
Consider following example test case
3
3 1 2 3
3 1 3 2
2 4 5
In this case map at index 1 (using 0-indexing) will have two key 1,2 and 3
In map{1} //map at index 1
Value mapped to value 1 = Max(abs(4-2), abs(5-2)) 1 = 31 = 3
// if 1 is first element, 2 is the last element
Value mapped to value 3 = Max(abs(4-1), abs(5-1)) * 1 = 4 * 1 = 4
// if 3 is first element, 1 would be last element
Value mapped to value 2 = Max(abs(4-3), abs(5-3)) = 2 * 1 = 2
// if 2 is first element, then 3 would be last element
In case map already has a mapping with same key, take maximum of two.
This was the basic working of map in my solution.
Now, when you solve any recursive problem, you often run something like solve(0 , 0) something like that, ryt??
Similarly, i took maximum and minimum of last array, mapped them to 0 in map{N-1}
These values start the recursive progress below.
// because best solution till now is 0
Now, the main loop // ar{i}{j} denote jth element in ith array given
For i = N-2 to 0 // loop 1 start
Int min = 1e7, max = 0 // ill use this later
For j = 0 to ar{i}.length // loop 2 start
Int current = ar{i}{j}, nextValue = ar{i}{j+1} //( ar{i}{0} if j == ar{i}.length-1 )
// observe, if cuurent value is last element in array, nextValue will be first element
min = min(min, nextValue) // min value fixed at first position
max = max(max, nextValue) // max value fixed at first position
Int temp = map{i}.get(nextValue) // if map already has some result stored, else 0.
For entry e:map{i+1} // loop 3 // looping through (i+1)th results
Int key = e.key; // key means first element in (i+1)th array
Long previousResult = e.value //best answer for key
temp = max(temp, abs(current-key)*(i+1) + previousResult) // according to formula given in problem
//end loop 3
map{i}.put(nextValue, temp) // best answer fixing nextValue at first position in ith array.
// end loop 2
Now comes the discarding part. The solution is completely a brute force solutuon without this
Array removal = new int{1e6+1}
Int removed = 0
Long maxResult = map{i}.get(max), minResult = map{i}.get(min) // best results fixing minimum and maximum value of ith array at first position.
For entry e : map{i} // loop 4
If( e.key != min &; e.key != max && e.value <= minResult && e.value <= maxResult) removal{removed++} = e.key //explained below
// end loop 4
// following loop just removes the useless entries which for sure do not give us best results, we just selected them in above loop
For int j = 0 to removed // loop 5
map{i}.remove(removal{j});
// end loop 5
// end loop 1
Now the answer of this problem is the maximum value mapped to any key in map{0}
The observation to remove values is that if any value other than min and max has a result smaller than both max and min, then the entries will never give optimal solution.
Consider three mapping in ith map as below
3 => 5
4 => 4
5 => 6
In i+1 th map
Entry 5 will always give better result than entry 4 for any value x < 4
And
Entry 3 will always give better result than entry 4 for any value x > 4
So, we can safely discard entry 4 without further ado, getting 100 points. Hurray!!!
Feel free to ask anything… 
Bonus challenge
Design a worst test case for this solution.
Hints for a worst test case
try maximizing following sum
Let a,b,c … n be the size of inner arrays
Sum = ab+ bc + cd … mn
And select elements in array in such a manner that entries deleted are minimum
Enjoy coding…
. Can u explain the time complexity of this solution and tell me how it passes.