解法：贪心

思维第一步

看到“任一元素加上或减去 value”，而且“可以操作任意次”，马上反馈出等价条件：

数 $x$ 可以变成任意满足 y mod value == x mod value 的数 $y$。

因此，我们可以把整个序列按元素取模的值分成 value 类，每一类元素都不会因为操作而变成其他类别里的元素。

思维第二步

既然我们要让“缺失的最小非负整数”最大，设第 $i$ 类里有 $k$ 个数，那么它们需要变成 $i, v + i, 2v + i, \cdots (k - 1)v + i$ 才能让 mex 尽可能大。

举个例子帮助大家理解，假设 $v = 5$，第 $2$ 类里有 $3$ 个数，那么它们需要变成 $2, 7, 12$ 才能让 mex 尽可能大。如果变成别的，比如 $2, 12, 17$，那因为缺失了 $7$（而且其他类别的数也没法变成 $7$），那 mex 至多就是 $7$ 了。如果是 $2, 7, 12$，那 mex 还有可能是 $17$，肯定这样做更优。

最终处理

既然我们已经确定了每个数都要变成什么，那完成变化以后，直接计算变化后序列的 mex 就是答案。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int v) {
        int n = nums.size();
        // vis[i] 表示变化后的序列里是否出现过元素 i
        // 答案肯定不超过 n
        // 因为最好情况就是 nums = [0, 1, ..., n - 1]，这样 mex = n
        bool vis[n + 1];
        memset(vis, 0, sizeof(vis));
        
        // cnt[i] 表示第 i 类元素目前有几个
        int cnt[v];
        memset(cnt, 0, sizeof(cnt));
        for (int x : nums) {
            // t 是元素 x 所属的类别
            int t = (x % v + v) % v;
            // y 是元素 x 应该变成什么数
            int y = cnt[t] * v + t;
            if (y < n) vis[y] = true;
            cnt[t]++;
        }
        
        // 计算变化后序列的 mex
        for (int i = 0; i <= n; i++) if (!vis[i]) return i;
        return -1;
    }
};

解法：枚举

这种一前一后两个子数组的题，一般考虑枚举分界点（比如第二个子数组的开头）。

维护 $f(i)$ 表示以第 $i$ 个元素为结尾，最长的单调递增子数组是多长；$g(i)$ 表示以第 $i$ 个元素为开头，最长的单调递增子数组是多长。那么我们枚举第二个子数组的开头 $b$，说明第一个子数组的结尾就是 $(b - 1)$，答案就是 $\max(\min(f(b - 1), g(b)))$。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        int f[n + 2], g[n + 2];
        f[0] = 0; g[n + 1] = 0;
        // 计算以第 i 个元素为结尾，最长的单调递增子数组是多长
        for (int i = 1; i <= n; i++) {
            if (i > 1 && nums[i - 2] < nums[i - 1]) f[i] = f[i - 1] + 1;
            else f[i] = 1;
        }
        // 计算以第 i 个元素为开头，最长的单调递增子数组是多长
        for (int i = n; i > 0; i--) {
            if (i < n && nums[i - 1] < nums[i]) g[i] = g[i + 1] + 1;
            else g[i] = 1;
        }
        int ans = 0;
        // 枚举第二个子数组的开头
        for (int i = 1; i <= n; i++) ans = max(ans, min(f[i - 1], g[i]));
        return ans;
    }
};

解法：DP

设 $f(i, j)$ 表示巫师 $j$ 完成药水 $i$ 的时间，且暂时不考虑这瓶药水后面的步骤。这个时间受到三个限制：

1. 巫师 $(j - 1)$ 需要先完成这个药水，巫师 $j$ 才能开始酿造，即 $f(i, j) \xleftarrow{\max} f(i, j - 1) + s_jm_i$。
2. 巫师 $j$ 需要先完成上一瓶药水才能开始酿造，即 $f(i, j) \xleftarrow{\max} f(i - 1, j) + s_jm_i$。
3. 巫师 $j$ 完成这瓶药水时，巫师 $(j + 1)$ 也要完成上一瓶药水，即 $f(i, j) \xleftarrow{\max} f(i - 1, j + 1)$。

这样我们就能算出巫师 $n$ 完成药水 $i$ 的时间。注意，由于 $f(i, j)$ 没有考虑这瓶药水后面的步骤，所以可能会出现 $f(i, j) + s_{j + 1}m_i < f(i, j + 1)$ 的情况。因此我们还要从 $f(i, n)$ 开始倒推，计算 $f(i, j) = f(i, j + 1) - s_{j + 1}m_i$，把每名巫师真实的完成时间算出来。

复杂度 $\mathcal{O}(nm)$。

参考代码（c++）

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();

        // 空间优化：去掉了 DP 的第一维
        long long f[n + 2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; i++) {
            // 正推计算巫师 j 完成药水 i，且不考虑后面步骤的时间
            for (int j = 1; j <= n; j++) f[j] = max(max(f[j - 1], f[j]) + skill[j - 1] * mana[i - 1], f[j + 1]);
            // 倒推计算巫师 j 完成药水 i 的真实时间
            for (int j = n - 1; j > 0; j--) f[j] = f[j + 1] - skill[j] * mana[i - 1];
        }

        return f[n];
    }
};

解法 1：模拟

按题意模拟即可，复杂度 $\mathcal{O}(n^2)$。

参考代码（c++）

###c++

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> f[2];
        f[0] = f[1] = vector<int>(n);
        f[n & 1] = nums;
        for (int i = n; i > 1; i--) for (int j = 0; j + 1 < i; j++) f[i & 1 ^ 1][j] = (f[i & 1][j] + f[i & 1][j + 1]) % 10;
        return f[1][0];
    }
};

解法 2：数学

考虑第 $i$（从 $0$ 开始）个数对答案的贡献，其实就是 $C_{n-1}^i$。由于模数不是质数，通过 扩展卢卡斯定理 求出所有组合数，答案就是 $\sum\limits_{i=0}^{n-1} C_{n-1}^i \times \text{nums[i]}$。复杂度 $\mathcal{O(n\log m)}$，其中 $m$ 是模数。