分治做法，每次找到区间的最小值，区间减去最小值，然后再分别处理左右区间。

虽然这种做法在随机数据，每次 mid 差不多在中间位置的时候，期望时间复杂度大概是 $O(n \log n)$ 的。

但是直接 $a_i = i$ 的数据就可以卡掉了，希望多加入一组这样的数据。

下面是分治的代码。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a[N];

int solve(int l, int r) {
	int mid = -1, mic = INT_MAX;
	for(int i = l; i <= r; ++i)
		if(a[i] < mic) {
			mic = a[i];
			mid = i;
		}
	int res = mic;
	for(int i = l; i <= r; ++i)
		a[i] -= mic;
	if(l < mid) res += solve(l, mid - 1);
	if(mid < r) res += solve(mid + 1, r);
	return res;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	cout << solve(1, n) << endl;
	return 0;	
}

更加保险的做法是加上给线段树来维护区间的信息。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n;
int a[N];

int ll, rr, cv;

struct xds {
#define lch(x) (x << 1)
#define rch(x) (x << 1 | 1)
	pair<int, int> mic[N * 4];
	void update(int u) { mic[u] = min(mic[lch(u)], mic[rch(u)]); }
	void build(int u, int l, int r) {
		if(l == r) return mic[u] = make_pair(a[l], l), void();
		int mid = l + r >> 1;
		build(lch(u), l, mid), build(rch(u), mid + 1, r);
		update(u);
	}
	pair<int, int> query(int u, int l, int r) {
		if(ll <= l && r <= rr) return mic[u];
		int mid = l + r >> 1;
		if(rr <= mid) return query(lch(u), l, mid);
		else if(mid < ll) return query(rch(u), mid + 1, r);
		else return min(query(lch(u), l, mid), query(rch(u), mid + 1, r));
	}
} tr;

int solve(int l, int r, int x) {
	ll = l, rr = r;
	pair<int, int> pr = tr.query(1, 1, n);
	int mid = pr.second;
	int d = pr.first - x;
	//cout << l << ' ' << r << ' ' << pr.first << ' ' << x << endl;
	int res = d;
	if(l < mid) res += solve(l, mid - 1, x + d);
	if(mid < r) res += solve(mid + 1, r, x + d);
	return res;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	tr.build(1, 1, n);
	printf("%d\n", solve(1, n, 0));
	return 0;	
}