NOI 2013 Q1

[smgfour]

The question for this problem is below:

A scientist wants to study how the rising sea level changes the landscape, in particular, how it changes the number of islands. He first investigates one-dimensional worlds. A one-dimensional world is represented by a sequence of non-negative integers {h0, h1, . . . , hn−1}, where each integer hi is the altitude at the location i. You are to code the function find_max_islands which takes in a list of n integers (5 <= n <= 10,000 representing the sequence {h0, h1, . . . , hn−1}. All numbers in the sequence are non-negative and smaller than 230. The function should then return an integer, which is the maximum number of islands. Your code should run within 1.0 seconds. You should not import any packages or modules.

And here is my code:

def find_max_islands(lst):
    maxislands = 1
    for sealevel in lst:
        flag = True # flag means canAdd
        numislands = 0
        for j in lst:
            if j <= sealevel:
                flag = True # can Add
            if flag and j > sealevel:
                flag = False # cannot Add
                numislands += 1 
        maxislands = max(maxislands,numislands) # find max num of islands after each iteration

    if lst==[] or sum(lst)==0:
        return 0
    return maxislands

The code covers all the cases correctly but takes too long to run. I suspect the possibility of it to be because the code is of function O(n^2). I want to know if it is possible to shorten the code to a function O(n log n) or anything else shorter.