ビルを壊さない場合に見えるビルを \(P_1 < \dots <P_K\) とします。また、\(P_0=0\) とし高さ \(0\) のビルが、\(P_{K+1}=N+1\) とし高さ \(\infty\) のビルがあるものとします。\(P_1,\ldots,P_K\) は \(O(N)\) で求めることができます。

\(K=N\) のとき、どのビルを壊しても見えるビルは 1 つ減るため、答えは \(N-1\) です。

\(K<N\) のとき、見えないビルを壊しても見えるビルの個数は変わらず \(K\) 個です。
見えるビル \(P_i\) を壊した場合、新たに見えるようになるビルは \(P_i+1\) から \(P_{i+1}-1\) の範囲にあるビルであって、ビル \(P_{i-1}\) より高く、高さの最大値を更新するものです。よってこれは愚直に調べることにより \(O(P_{i+1}-P_i)\) で求めることができます。
これを全ての \(i\) について行うことで、\(O(N)\) で答えを求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i=0; i<n; i++) cin >> h[i];

  vector<int> p;
  int m = 0;
  for(int i=0; i<n; i++){
    if(h[i] > m){
      m = h[i];
      p.push_back(i);
    }
  }

  int k = p.size();
  if(k == n){
    cout << n-1 << endl;
    return 0;
  }

  // 末尾に番兵を追加
  p.push_back(n);
  int ans = k;
  for(int ii=0; ii<k; ii++){
    int m;
    if(ii == 0){
      m = 0;
    }else{
      m = h[p[ii-1]];
    }
    int cnt = 0;
    for(int i=p[ii]+1; i<p[ii+1]; i++){
      if(h[i] > m){
        m = h[i];
        cnt++;
      }
    }
    ans = max(ans, k - 1 + cnt);
  }

  cout << ans << endl;
}

実装例 (Python)

N = int(input())
H = list(map(int, input().split()))

P = []
m = 0
for i in range(N):
  if H[i] > m:
    m = H[i]
    P.append(i)

K = len(P)
if K == N:
  print(N-1)
  exit()

# 末尾に番兵を追加
P.append(N)
ans = K
for ii in range(K):
  m = 0 if ii == 0 else H[P[ii-1]]
  cnt = 0
  for i in range(P[ii]+1, P[ii+1]):
    if H[i] > m:
      m = H[i]
      cnt += 1
  ans = max(ans, K - 1 + cnt)

print(ans)