一. 题目

二. 思路

三. 代码

using LL=long long;
const int N=1e5+10, BASE=1, MOD=1e9+7, INF=2e9;

class DP
{
public:
    int cnt[N], maxv;
    LL f[N];

public:
    void init(vector<int>& nums)
    {
        fill(cnt, cnt+N, 0);
        fill(f, f+N, 0);
        maxv=reduce(nums.begin(), nums.end(), -INF, [](const int &a, const int &b)->int{
            return max(a, b);
        });
    }

    int work(vector<int>& nums)
    {
        init(nums);//初始化
        for(auto &x:nums)//从前往后枚举，所以无论+1还是-1都是前面的子序列
        {
            LL c=cnt[x-1+BASE]+cnt[x+1+BASE]+1;
            cnt[x+BASE]=(cnt[x+BASE]+c)%MOD;
            f[x+BASE]=(f[x+BASE]+f[x-1+BASE]+f[x+1+BASE]+x*c%MOD)%MOD;
        }
        //+2是因为最大偏移可能到2
        return reduce(f, f+maxv+2, 0, [](const int &a, const int &b)->int{
            return (a+b)%MOD;
        });
    }
}dp;

class Solution {
public:
    int sumOfGoodSubsequences(vector<int>& nums) {
        return dp.work(nums);
    }
};