排序列表中的最大總和

Question

我知道這不是一個編程問題，但它涉及編程和一些數學。 假設我有一套N項目，都有自己的觀點，並按照他們的等級排序。例如：

list1 = { // N = 4 
1: (item1, points: 100, rank:1), 
2: (item2, points:55, rank:2), 
3: (item3, points:55, rank:2), 
4: (item4, points:45, rank:3) } 

等等。 list2是這4（N）個項目的另一個列表，但具有不同的點，因此不同的等級。我試圖對這兩個列表進行比較，比如兩個列表中的項目排名的差異總和。

例如：

list2 = { // N = 4 
1: (item4, points: 10, rank:1), 
2: (item3, points:9, rank:2), 
3: (item2, points:8, rank:3), 
4: (item1, points:7, rank:4) } 

在這種情況下

差異S =（ITEM1級差+ ITEM2 「」 + ....）的總和 S = 3 + 1 + 0 + 2 = 6

，以便將它與最壞的情況相比，我需要這筆錢對不同施氮的最差值。

那麼，以N計的S的最大值是多少？ S_max（N）=？

感謝您的任何幫助。

Answer 1

我不知道理解，但對於長度爲N 2所列出的最差值將是列表1每個項目排名1和表2排名相同（不是唯一的最壞的情況下沒有項目，但明確最壞的情況下）：

sum = (1-1)+(2-1)+...+((n-1)-1)+(n-1) 
    = 0 + 1 + ... + (n-2) + (n-1) 
    = n(n-1)/2