LC-0845 Medium LeetCode

845. Longest Mountain in Array

Array Two Pointers Dynamic Programming Enumeration

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 41% Topics: Array, Two Pointers, Dynamic Programming, Enumeration

Reading material

Arrays & Hashing 12 min Two Pointers 9 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)


class Solution(object):
    def longestMountain(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        result, up_len, down_len = 0, 0, 0
        for i in xrange(1, len(A)):
            if (down_len and A[i-1] < A[i]) or A[i-1] == A[i]:
                up_len, down_len = 0, 0
            up_len += A[i-1] < A[i]
            down_len += A[i-1] > A[i]
            if up_len and down_len:
                result = max(result, up_len+down_len+1)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT