题目描述

给定 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 号石子。可以只选择一个石子，此时选取任何石子均为合理方案。
你的选择方案不仅需要合理，而且还要使得选中石子的价值总和尽可能大。

请计算并输出价值总和的最大可能值。

输入格式
第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
一个整数，表示选中石子的价值总和的最大可能值。

数据范围
前三个测试点满足 1≤n≤10。
全部测试点满足 1≤n≤2×105，1≤ai≤4×105。

样例

输入样例1：
6
10 7 1 9 10 15
输出样例1：
26
输入样例2：
1
400000
输出样例2：
400000
输入样例3：
7
8 9 26 11 12 29 14
输出样例3：
55

算法1

(数学运算-分组) $O(n)$

x - y = ax - ay
得到 ax - x = ay - y

时间复杂度

参考文献

python3 代码

from collections import defaultdict

n = int(input())
a = [int(x) for x in input().split()]

diff_sum = defaultdict(int)
for i, x in enumerate(a):
    diff = x - i
    diff_sum[diff] += x

res = 0
for _, num_sum in diff_sum.items():
    res = max(res, num_sum)

print(res)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main()
{
    int n;    cin >> n;
    long long a[n];
    for (int i = 0; i < n; i ++)
        cin >> a[i];

    unordered_map<int, long long> diff__num_sum;
    for (int i = 0; i < n; i ++)
    {
        int diff = a[i] - i;
        diff__num_sum[diff] += a[i];
    }

    long long res = 0;
    for (auto [_, num_sum] : diff__num_sum)
        res = max(res, num_sum);

    cout << res << endl;

    return 0;
}

java 代码

import java.util.* ;

public class Main
{
    public static void main(String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long [] a = new long [n];
        for (int i = 0; i < n; i ++)
            a[i] = scan.nextLong();

        Map<Integer, Long> diff__num_sum = new HashMap<>();
        for (int i = 0; i < n; i ++)
        {
            int diff = (int)(a[i] - i);
            if (diff__num_sum.containsKey(diff) == false)
            {
                diff__num_sum.put(diff, a[i]);
            }
            else
            {
                diff__num_sum.put(diff, diff__num_sum.get(diff) + a[i]);
            }
        }

        long res = 0;
        for (Map.Entry<Integer, Long> d_sum: diff__num_sum.entrySet())
        {
            res = Math.max(res, d_sum.getValue());
        }

        System.out.println(res);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla