给定 n 个石子,编号为 1∼n。其中第 i 个石子的价值为 ai。
你需要从中任意挑选若干个石子,并将挑选好的石子按照编号从小到大的顺序排成一排。
选中的石子在排好序后需要满足,对于任意两个相邻的石子(不妨设它们的编号为 x,y),x−y=ax−ay 均成立。
例如,当有 n=8 个石子,石子价值分别为 [3,4,4,6,6,7,8,9] 时,一些合理的选择方案如下:
- 选择 1,2,4 号石子,它们的价值分别为 3,4,6。1 号石子与 2 号石子相邻,2−1=4−3 成立。2 号石子与 4 号石子相邻,4−2=6−4 成立。所以方案合理。
- 选择 7 号石子。可以只选择一个石子,此时选取任何石子均为合理方案。
你的选择方案不仅需要合理,而且还要使得选中石子的价值总和尽可能大。
请计算并输出价值总和的最大可能值。