**Solution Notes:** We can solve this problem in O(N log N) time
by simulating the rising water line by visiting the cells of the
landscape in increasing order by height. Let us think of the landscape
initially as a large string of length N, where each character is
either L (for land) or W (for water). Initially, this string is set
to "LLLL..LLLL", since no land is covered by water. After sorting the
cells in the landscape by height, let us now switch the Ls to Ws as we
visit cells in order of height, keeping a running count of the number
of islands. Whenever we change LLL to LWL (i.e., when we change an L
to a W and the neighboring cells are both L), we increment the island
count, since we have split one island into two. Whenever we change
WLW to WWW (i.e., when we change an L to a W and the neighboring cells
are both W), we decrement the island count, since we have destroyed an
island.

```
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define nmax (5 + 100000)
struct land {
int x, h;
};
inline bool operator<(land a, land b) {
return a.h < b.h;
}
land lands[nmax];
bool underwater[nmax];
int main() {
freopen("islands.in","r",stdin);
freopen("islands.out","w",stdout);
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &lands[i].h);
lands[i].x = i;
}
memset(underwater, 0, n);
sort(lands, lands + n);
int numIslands = 1;
int maxIslands = 1;
for(int i = 0; i < n; i++) {
int x = lands[i].x;
underwater[x] = true;
bool landToLeft = (x > 0 && !underwater[x-1]);
bool landToRight = (x < n-1 && !underwater[x+1]);
if(landToLeft && landToRight) {
numIslands++;
}
else if(!landToLeft && !landToRight) {
numIslands--;
}
if((i == n-1 || lands[i+1].h > lands[i].h) && numIslands > maxIslands) {
maxIslands = numIslands;
}
}
printf("%d\n", maxIslands);
}
```