448C - Painting Fence - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 7;
int a[N];
int func(int l, int r) {
	int len = r - l;
	if (len <= 0) {
		return 0;
	}
	if (len == 1) {
		if (a[l] == 0) return 0;
		else return 1;
	}
	int k = 1e9 + 7;
	int p = 0;
	for (int i = l; i < r; i++) {
		if (k > a[i]) {
			p = i;
			k = a[i];
		}
	}
	int j = k;
	for (int i = l; i < r; i++) {
	     a[i] -= j;
	     if (a[i] < 0) a[i] = 0;
	}
	return min(len, (func(l, p) + func(p + 1, r) + k));
	
}
int main () {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int h = func(0, n);
	cout << h;
}