Why can't it be solved with a greedy algorithm?

Question

C++ / C#

There is a challenge: https://codeforces.com/contest/1400/problem/E
My code:

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int main() {
  IOS;
  int n;
  cin >> n;
  vector<int>a;
  a.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  int len = 0;
//	int not1 = 0;
  //int y1 = 0;
  long long ans = 0;
  bool f = false;
  a.push_back(0);
  for (int i = 0; i <= n; i++) {
    if (a[i] == 0) {
      if (len > 1) {
        ans += 1;
        for (int j = i - len; j < i; j++) {
          a[j]--;
        }
      }
      //ans += len;
      len = 0;
      f = false;
    }
    else {
      if (f && a[i]>1) { 
        ans += 2; len = 0; 
        a[i] = 0;
        a[i - 1] = 0;
      }
      else len++;
      if (a[i] > 1) f = true;
      else f = false;
  //		if (a[i] == 1) y1++;
  //		else not1++;
    }
  }
  for (int i = 0; i < n; i++) {
    if (a[i] > 0) ans++;
  }
  cout << ans << "\n";
}

The idea is that, first go through the continuous non-zero sub-arrays, subtract 1 from each element, then go through the array again and add the number of elements > 0 to the answer,

if (f && a[i]>1) { 
        ans += 2; len = 0; 
        a[i] = 0;
        a[i - 1] = 0;
      }

It is necessary that under an array, for example, 2.2 is removed in 2 moves, and not in 4.
But still, the solution is wrong, why?

Answer 1

Why doesn't greed work? You yourself brought a test on which such greed does not work.
I can give you an example. In {1, 2, 3, 2, 1} - the answer is 3. Here you need to delete the segment 1..5, then 2..4, then 1 occurrence of element 3, If the form is slightly different, for example {1, 100, 1000, 100, 1} - then the answer is 4. After the first deletion of the segment, you must delete the numbers one by one.
In general, a greedy solution does not work until proven otherwise.
One of your observations is indeed true - in the optimal solution, some segments are removed first, and then the entire remaining elements are removed one at a time.

This can be proven like this:

Рассмотрим какое-то решение (последовательность действий). Перенесем все удаления одиночных элементов в самый конец, возможно изменив количество удаляемых за раз элементов. Кроме того, объеденим несколько операций удаления одного и того же элемента в одну, просуммировав количества удаленных элементов. Все шаги-отрезки все так же можно выполнить, потому что мы только перетащили какие-то операции за них, поэтому перед шагом количество элементов могло только увеличится, а значит весь отрезок все так же не содержит нулей. Это решение имеет такое же количество шагов или меньше. Значит можно искать оптимальное решение именно такого вида.

Many greeds are proved by similar reasoning, without applying matroid theory : Consider the answer, somehow change it so that it has the properties that your greed produces. if at the same time it becomes no worse - you have proved that it is possible to do so.
Until you prove your algorithm in this way, you can safely assume that there is some other test where it will give a non-optimal answer.
Hint 1: Look at the limits. n is only 5000. So, the solution for the square is implied. Look at the tags.
Hint2: You can look at this problem like this - there are turrets made of cubes of height a[i]. You can either paint the vertical segment of the tower at the very top at a time, or paint some horizontal segment of the cubes. It is necessary to paint all the cubes in the least number of steps. Here it is only not obvious why it is necessary to paint horizontal segments, because several operations for deleting a segment can intersect. But here reasoning as above will help, by changing any answer. These operations can be folded like boards, in the form of pyramids, incl. the upper operations lie entirely within the lower operations. This will make the answer worse.
Another hint, think about how you can remove the highest standing cube, what are the options?