gistfile1.txt

def getPeaks(A):
    peaks = [-1] * len(A)
    for i in xrange(1, len(A) - 1):
        if A[i] > A[i - 1] and A[i] > A[i + 1]:
            peaks[i] = 0
    return peaks

def getNumPeaks(A):
    N = len(A)
    peaks = getPeaks(A)
    numPeaks = 0
    for i in xrange(N):
        if peaks[i] == 0:
            numPeaks += 1
    return numPeaks

def buildNextPeak(A):
    N = len(A)
    peaks = getPeaks(A)
    nexkPeak = [0] * N
    nexkPeak[N - 1] = -1
    for i in xrange(N -2, 0, -1):
        if peaks[i] == 0:
            nexkPeak[i] = i
        else:
            nexkPeak[i] = nexkPeak[i + 1]  
    return nexkPeak

def solution(A):
    N = len(A)
    nextPeakArray = buildNextPeak(A)
    startPos = nextPeakArray[1]
    from math import sqrt, floor
    K = int(floor(sqrt(N)))
    for k in xrange(K, 0, -1):
        print "k is ",k
        numFlag = 1
        currentPos = startPos
        print "start at ", currentPos
        while currentPos + k < N - 1 and currentPos != -1:
            currentPos = nextPeakArray[currentPos + k]
	    if currentPos != -1
                numFlag +=1 
                print "pos is", currentPos
                print "num of flags ", numFlag
#            if numFlag == 5:
#                break
        if numFlag == k:
            return numFlag


if __name__ == '__main__':
#    N = [1,5,3,4,3,4,1,2,3,4,6,2]
    N = [0, 0, 0, 0, 0, 1, 0, 1, 0, 1]
    print getPeaks(N)
    print buildNextPeak(N)
    print solution(N)