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);

}