最近在 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1711686700.A.EAA.html ※ 编辑: Pttgambler (220.138.126.248 台湾), 03/29/2024 12:33:11