题目描述

给你一个下标从 0  开始的整数数组 $nums$ 。

$nums$ 一个长度为 $k$ 的 子序列  指的是选出 $k$ 个 下标  $i_0 < i_1 < ... < i_{k-1}$ ，如果这个子序列满足以下条件，我们说它是 平衡的  ：

• 对于范围 $[1, k - 1]$ 内的所有 $j$ ，$nums[i_j] - nums[i_{j-1}] >= i_j - i_{j-1}$ 都成立。

$nums$ 长度为 $1$ 的 子序列  是平衡的。

请你返回一个整数，表示 $nums$  平衡  子序列里面的 最大元素和  。

一个数组的 子序列  指的是从原数组中删除一些元素（ 也可能一个元素也不删除 ）后，剩余元素保持相对顺序得到的 非空  新数组。

输入格式

第一行一个整数 $n$ 表示数组长度；

第二行 $n$ 个空格隔开的整数表示数组中的元素。

输出格式

一行一个整数表示答案。

示例 1：

4
3 3 5 6

14

解释:

这个例子中，选择子序列 [3,5,6] ，下标为 0 ，2 和 3 的元素被选中。

nums[2] - nums[0] >= 2 - 0 。

nums[3] - nums[2] >= 3 - 2 。

所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。

包含下标 1 ，2 和 3 的子序列也是一个平衡的子序列。

最大平衡子序列和为 14 。

示例 2：

4
5 -1 -3 8

13

解释: 这个例子中，选择子序列 [5,8] ，下标为 0 和 3 的元素被选中。 nums[3] - nums[0] >= 3 - 0 。 所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。 最大平衡子序列和为 13 。

示例 3：

2
-2 -1

-1

解释: 这个例子中，选择子序列 [-1] 。 这是一个平衡子序列，而且它的和是 nums 所有平衡子序列里最大的。

提示：

• $1 <= nums.length <= 10^5$
• $-10^9 <= nums[i] <= 10^9$

SOURCE

平衡子序列的最大和