最近在 Leetcode 上面看到有人分享的一題線上測驗，
想了一段時間都沒有想出暴力解以外的做法，所以來這裡問看看。
https://leetcode.com/discuss/interview-question/4902893/recent-goldman-sachs-oa-questionanybody-with-a-optimal-approach
In a tranquil village school, there are two students named Ramu and Sonu,
each possessing a collection of N distinct chalks. Each student's chalks are
of different lengths, represented by N positive integers. Ramu has arranged
his collection of N chalks in a specific order based on their lengths. Sonu
is eager to organize his own N chalks in a way that mimics Ramu's arrangement
in terms of length changes i.e. if in Ramu's arrangement the kth chalk is
bigger than the k+1th chalk, in Sonu's arrangement also the kth chalk will be
bigger than the k-1th chalk; alternately if it is smaller in Ramu's
arrangement, then it will be smaller in Sonu's as well.Sonu was busy
arranging his chalks, when his teacher told him to also maximize the overall
"niceness" of his arrangement. Here, niceness' is defined as the sum of the
absolute length differences between all adjacent chalks in the
arrangement.Write a program to assist Sonu in achieving both the objectives:
first, to mimic Ramu's length variation order, and second, to maximize the
overall niceness of the arrangement.
Sample Input1:
4
5 7 4 9
1 2 3 4
Sample Output1:
7
Explanation1:
Given N=4.
Ramu's chalks are arranged in the order of their length as 5 7 4 9, which
corresponds to an increase- decrease-increase pattern of arrangement. Sonu
has the chalk collection 12:34.
To mimic Ramu's chalk arrangement order of increase-decrease-increase, Sonu
can arrange his chalk in the following five ways.
(1,3,2,4)-niceness-> |1-3|+|3-2|+|2-4|=2+1+2=5
(1,4,2,3)-niceness-> |1-4|+|4-2|+|2-3|=3+2+1=6
(2,3,1,4)-niceness-> |2-3|+|3-1|+|1-4|=1+2+3=6
(2,4,1,3)-niceness-> |2-4|+|4-1|+|1-3|=2+3+2=7
(3,4,1,2)-niceness-> |3-4|+|4-1|+|1-2|=1+3+1-5
As can be seen, the maximum niceness possible is 7, which is printed as
output.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.138.126.248 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1711686700.A.EAA.html
※ 編輯: Pttgambler (220.138.126.248 臺灣), 03/29/2024 12:33:11