nowcoder减成一（差分）

链接：https://ac.nowcoder.com/acm/contest/5758/B
来源：牛客网

题目描述

存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。
数据保证一定有解。

输入描述:

输入t，代表有t组数据。每组数据输入n，代表有n个数。接下来一行输入n个数，数字大小小于1e6。(t<=1000，n<1e5，∑n < 1e6)

输出描述:

每组数据输出一个整数代表最少需要操作的次数。

示例1
复制

输入

1 6 1 3 5 2 7 1
复制

输出

9

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int q[N];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) scanf("%d",&q[i]);
        long res = 0;
        while (q[0] != 1) {
            res++;
            for (int i = 0; i < n; ++i) 
                if (q[i] != 1) q[i]--;
                else break;
        }
        for (int i = 1; i < n; ++i) res += max(q[i] - q[i-1], 0);
        cout << res << endl;
    }
    return 0;
}