寻找排列的最大得分：问题探究与最优策略求解

问题定义 #

考虑长度为n（n>2）的排列P，即整数1到n的任意顺序（例如n=7时，P=[6,5,2,3,7,1,4]）。排列的得分定义为满足条件P[i] >= P[i+1] + P[i+2]的索引i（0≤i≤n-3）的数量，上述示例得分为2（对应i=1、5）。

已知暴力求解的最大得分结果 #

n = 3; max = 1 (3 2 1)
n = 4; max = 2 (4 3 1 2)
n = 5; max = 2 (5 4 3 1 2)
n = 6; max = 2 (6 4 2 1 3 5)
n = 7; max = 3 (7 5 1 4 6 3 2)*
n = 8; max = 4 (8 5 3 2 7 6 1 4)
n = 9; max = 4 (9 8 5 3 2 7 6 1 4)
n = 10; max = 5 (10 8 2 6 9 5 4 1 3 7)
n = 11; max = 5 (11 10 8 2 6 9 5 4 1 3 7)
n = 12; max = 6 (12 7 3 4 10 9 1 6 11 8 2 5)
.
n = 15; max (currently) = 8; (15 13 1 11 9 2 7 14 10 4 6 12 8 3 5)
.
n = 20; max (currently) = 10 (20 15 1 10 19 14 2 9 18 13 3 8 17 12 4 7 16 11 5 6)

已发现的两种构造策略 #

• 分块构造：将排列拆分为多个固定长度的子块，每个子块独立贡献得分点。例如n=20的构造方式：

  20 15 1 10
  19 14 2 9
  18 13 3 8
  17 12 4 7 
  16 11 5 6
  

  每个4元素块可贡献2个得分点，5个块总计获得10个得分。

• 合并得分块：对已有的得分块进行拼接或扩展，适配非标准长度的n。例如n=15的构造：

  15 13 1 11
          11 9 2 7 | 14 10 4 6 | 12 8 3 5
  

核心疑问 #

是否存在计算任意n对应的排列最大得分的公式或最优构造策略？

目前这个问题还没有找到通用的闭合公式，但已有构造性策略能逼近或达到已知的最大得分：

1. 标准化分块策略：对于n为4的倍数的情况，采用4元素分块构造，每个块设计为满足两次得分条件的结构，能稳定获得n/2的得分，这是当前已知的高效构造方式。
2. 扩展适配策略：对于非4倍数的n，可基于较小n的最优排列进行扩展（如在n=10的最优排列前添加11得到n=11的最优排列），这种方式能保留原有得分点，避免额外损失。

从已知数据来看，最大得分的增长趋势接近floor(n/2)，但部分n（如n=5、6）会低于这个值，说明存在边界情况需要调整构造逻辑。目前学界尚未证明这个上界是否对所有n都可达，也没有统一公式能直接计算任意n的最大得分，更多是通过构造性方法探索最优解。

内容的提问来源于stack exchange，提问作者user31824378