Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)
Given an array A of integers, return the length of the longest mountain. 
Return 0 if there is no mountain.
Example 1:
Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:
Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Follow up:

Can you solve it using only one pass?
Can you solve it in O(1) space?

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Amortized analysis

Data structures

Complete search

Starter code: class Solution:
    def longestMountain(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def longestMountain(self, A: List[int]) -> int:
		up = 0
		down = 0
		ans = 0
		for i in range(0, len(A) - 1):
			if A[i] < A[i + 1]:
				if down == 0:
					up += 1
				else:
					up = 1
					down = 0
			elif A[i] > A[i + 1]:
				if up > 0:
					down += 1
					mountain = up + down + 1
					if ans < mountain:
						ans = mountain
			else:
				up = 0
				down = 0
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		leftpivot = 0
		rightpivot = 0
		ascendign = False
		descending = False
		changes = 0
		highest = 0
		while leftpivot < len(A):
			rightpivot = leftpivot
			if rightpivot + 1 < len(A) and A[rightpivot] < A[rightpivot + 1]:
				while rightpivot + 1 < len(A) and A[rightpivot] < A[rightpivot + 1]:
					rightpivot += 1
				if rightpivot + 1 < len(A) and A[rightpivot] > A[rightpivot + 1]:
					while rightpivot < len(A) - 1 and A[rightpivot] > A[rightpivot + 1]:
						rightpivot += 1
					highest = max(highest, rightpivot + 1 - leftpivot)
			leftpivot = max(rightpivot, leftpivot + 1)
		return highest


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) < 3:
			return 0
		prev_height = None
		peaks = [0 for _ in range(len(A))]
		has_increment = False
		for idx in range(len(A)):
			if prev_height is not None:
				if prev_height < A[idx]:
					peaks[idx] = peaks[idx - 1] + 1
					has_increment = True
				else:
					if has_increment:
						peaks[idx - 1] += 1
					peaks[idx] = 0
					has_increment = False
			prev_height = A[idx]
		print(peaks)
		prev_height = None
		max_so_far = 0
		has_increment = False
		for idx in range(len(A) - 1, -1, -1):
			if prev_height is not None:
				if prev_height < A[idx]:
					peaks[idx] += peaks[idx + 1] + 1
					has_increment = True
				else:
					if has_increment and prev_height > A[idx]:
						max_so_far = max(max_so_far, peaks[idx + 1])
					peaks[idx] = peaks[idx]
					has_increment = False
			prev_height = A[idx]
		print(peaks)
		return max_so_far


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) < 3:
			return 0
		n = len(A)
		(ups, downs) = ([0] * n, [0] * n)
		(i, j) = (0, n - 1)
		while i < n - 1:
			if A[i] < A[i + 1]:
				ups[i + 1] = ups[i] + 1
			i += 1
		while j > 0:
			if A[j] < A[j - 1]:
				downs[j - 1] = downs[j] + 1
			j -= 1
		print((ups, downs))
		longest = [u + d + 1 for (u, d) in zip(ups, downs) if u and d]
		return max(longest) if longest else 0


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		N = len(A)
		prefix = [1] * N
		suffix = [1] * N
		for (i, num) in enumerate(A[1:], 1):
			i_rev = N - i - 1
			prefix[i] = prefix[i - 1] + 1 if A[i - 1] < num else 1
			suffix[i_rev] = suffix[i_rev + 1] + 1 if A[i_rev] > A[i_rev + 1] else 1
		ans = 0
		for (i, num) in enumerate(A):
			left = prefix[i]
			right = suffix[i]
			length = left + right - 1
			if length >= 3 and min(left, right) > 1:
				ans = max(ans, length)
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		leftIncreasing = [0 for x in range(len(A))]
		rightIncreasing = [0 for x in range(len(A))]
		for x in range(1, len(A)):
			if A[x] > A[x - 1]:
				leftIncreasing[x] += leftIncreasing[x - 1] + 1
			if A[len(A) - 1 - x] > A[len(A) - x]:
				rightIncreasing[len(A) - 1 - x] += rightIncreasing[len(A) - x] + 1
		result = 0
		for x in range(len(A)):
			if leftIncreasing[x] and rightIncreasing[x]:
				result = max(result, leftIncreasing[x] + rightIncreasing[x] + 1)
		return result if result >= 3 else 0


class Solution:

	def longestMountain(self, A):
		(up, down) = ([0] * len(A), [0] * len(A))
		for i in range(1, len(A)):
			if A[i] > A[i - 1]:
				up[i] = up[i - 1] + 1
		for i in range(len(A) - 1)[::-1]:
			if A[i] > A[i + 1]:
				down[i] = down[i + 1] + 1
		print(down)
		print(up)
		return max([u + d + 1 for (u, d) in zip(up, down) if u and d] or [0])


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) < 3:
			return 0
		longestMountain = 0
		for i in range(1, len(A) - 1):
			if A[i - 1] < A[i] > A[i + 1]:
				left = right = i
				while left > 0 and A[left - 1] < A[left]:
					left -= 1
				while right + 1 < len(A) and A[right + 1] < A[right]:
					right += 1
				mountainLength = right - left + 1
				longestMountain = max(longestMountain, mountainLength)
		return longestMountain


class Solution:

	def longestMountain(self, a: List[int]) -> int:
		ml = 0
		i = 0
		while i < len(a):
			c = 0
			if i + 1 < len(a) and a[i + 1] > a[i]:
				c = 1
				while i + 1 < len(a) and a[i + 1] > a[i]:
					c = c + 1
					i = i + 1
				while i + 1 < len(a) and a[i + 1] < a[i]:
					c = c + 1
					ml = max(c, ml)
					i = i + 1
			else:
				i = i + 1
		return ml


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		idx = 0
		big = 0
		while idx + 1 < len(A):
			long = 1
			if A[idx + 1] > A[idx]:
				while idx + 1 < len(A) and A[idx + 1] > A[idx]:
					idx += 1
					long += 1
			else:
				idx += 1
				continue
			if idx + 1 < len(A) and A[idx + 1] < A[idx]:
				while idx + 1 < len(A) and A[idx + 1] < A[idx]:
					idx += 1
					long += 1
			else:
				idx += 1
				continue
			big = max(long, big)
		return big if big >= 3 else 0


class Solution:

	def longestMountain(self, A):
		res = up = down = 0
		for i in range(1, len(A)):
			if down and A[i - 1] < A[i] or A[i - 1] == A[i]:
				up = down = 0
			up += A[i - 1] < A[i]
			down += A[i - 1] > A[i]
			if up and down:
				res = max(res, up + down + 1)
		return res


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		n = len(A)
		left_inc = [0] * n
		for i in range(1, n):
			if A[i] > A[i - 1]:
				left_inc[i] = 1 + left_inc[i - 1]
		print(left_inc)
		right_inc = [0] * n
		for i in range(n - 2, -1, -1):
			if A[i] > A[i + 1]:
				right_inc[i] = 1 + right_inc[i + 1]
		print(right_inc)
		res = 0
		for i in range(n):
			if left_inc[i] != 0 and right_inc[i] != 0:
				res = max(res, left_inc[i] + right_inc[i] + 1)
		return res if res >= 3 else 0


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) == 0:
			return 0
		n = len(A)
		peak = None
		maxMountainLen = 0
		i = 1
		while i + 1 < n:
			if A[i - 1] < A[i] and A[i] > A[i + 1]:
				left = right = i
				while left - 1 >= 0 and A[left - 1] < A[left]:
					left -= 1
				while right + 1 < n and A[right + 1] < A[right]:
					right += 1
				maxMountainLen = max(maxMountainLen, right - left + 1)
				i = right + 1
			else:
				i += 1
		return maxMountainLen


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		i = 0
		answer = 0
		while i < len(A) - 1:
			j = i + 1
			visited_top = False
			while j < len(A):
				print(i, j)
				if A[j] > A[j - 1]:
					if visited_top:
						break
				if A[j] < A[j - 1]:
					if not visited_top:
						if j - i == 1:
							break
						visited_top = True
				if A[j] == A[j - 1]:
					break
				j += 1
			if visited_top and j - i > 2:
				answer = max(answer, j - i)
			i = j
			if visited_top:
				i -= 1
		return answer


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		import copy
		if not A:
			return 0
		dp = []
		B = copy.deepcopy(A)
		B.insert(0, A[0])
		B.append(A[-1])
		for i in range(1, len(B) - 1):
			if B[i - 1] < B[i] and B[i + 1] < B[i]:
				dp.append(i - 1)
		ret = []
		A.append(A[-1])
		for top in dp:
			left = top
			while A[left - 1] < A[left] and left > 0:
				left -= 1
			right = top
			while A[right + 1] < A[right]:
				right += 1
			print(right, left)
			ret.append(right - left + 1)
		print(dp, ret)
		return max(ret) if ret else 0


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if not A or len(A) == 1:
			return 0
		m = len(A)
		(up, down) = ([0 for i in range(m)], [0 for i in range(m)])
		(up[0], down[-1]) = (0, 0)
		for i in range(1, m):
			j = m - 1 - i
			if A[i] > A[i - 1]:
				up[i] = up[i - 1] + 1
			else:
				up[i] = 0
			if A[j] > A[j + 1]:
				down[j] = down[j + 1] + 1
			else:
				down[j] = 0
		ans = 0
		for i in range(m):
			if up[i] and down[i]:
				ans = max(ans, up[i] + down[i] + 1)
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		ans = 0
		temp = 0
		trend = False
		if len(A) < 3:
			return 0
		good = False
		for i in range(1, len(A)):
			diff = A[i] - A[i - 1]
			if diff > 0:
				if not trend:
					good = True
					trend = True
					temp = 2
				else:
					temp = max(temp + 1, 2)
			elif diff < 0:
				if trend:
					trend = False
					temp = max(temp + 1, 2)
					ans = max(ans, temp)
				else:
					temp = max(temp + 1, 2)
					if good:
						ans = max(ans, temp)
			else:
				temp = 0
				trend = False
				good = False
			print(A[i], temp, trend, ans)
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) < 3:
			return 0
		(up, down, Max) = ([1] * len(A), [1] * len(A), 0)
		for i in range(1, len(A)):
			if A[i] > A[i - 1]:
				up[i] = up[i - 1] + 1
		for i in range(len(A) - 2, -1, -1):
			if A[i] > A[i + 1]:
				down[i] = down[i + 1] + 1
		for i in range(1, len(A) - 1):
			if A[i - 1] < A[i] > A[i + 1]:
				Max = max(Max, up[i] + down[i] - 1)
		return Max


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		N = len(A)
		up = [1] * N
		for i in range(1, N):
			if A[i] > A[i - 1]:
				up[i] += up[i - 1]
		down = [1] * N
		for i in range(N - 2, -1, -1):
			if A[i] > A[i + 1]:
				down[i] += down[i + 1]
		return max([u + d - 1 for (u, d) in zip(up, down) if u > 1 and d > 1 and (u + d - 1 >= 3)] or [0])


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if not A:
			return 0
		rising = None
		curr = 0
		best = 0
		prev = None
		for (i, x) in enumerate(A):
			print((i, ':', x, 'curr', curr))
			if prev is None:
				prev = x
				curr = best = 1
				continue
			if rising is None and x < prev:
				prev = x
				continue
			if rising is None and x > prev:
				rising = True
				prev = x
				curr = 2
				continue
			if rising and x > prev:
				curr += 1
			elif not rising and x < prev:
				curr += 1
			elif x == prev:
				rising = None
				best = max(best, curr)
			elif rising and x < prev:
				rising = False
				curr += 1
			elif not rising and x > prev:
				best = max(best, curr)
				rising = True
				curr = 2
			prev = x
		if rising is not None and (not rising):
			best = max(best, curr)
		return 0 if best < 3 else best


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		N = len(A)
		start = 0
		ans = 0
		while start < N:
			end = start
			if end + 1 < N and A[end] < A[end + 1]:
				while end + 1 < N and A[end] < A[end + 1]:
					end += 1
				if end + 1 < N and A[end] > A[end + 1]:
					while end + 1 < N and A[end] > A[end + 1]:
						end += 1
					ans = max(ans, end - start + 1)
			start = max(end, start + 1)
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) == 0:
			return 0
		increasing = False
		count = -float('inf')
		last = A[0]
		max_len = 0
		for i in range(1, len(A)):
			if A[i] > last and increasing:
				count += 1
			elif A[i] > last and (not increasing):
				count = 2
				increasing = True
			elif A[i] < last and increasing:
				count += 1
				increasing = False
				max_len = max(max_len, count)
			elif A[i] < last and (not increasing):
				count += 1
				max_len = max(max_len, count)
			else:
				if not increasing:
					max_len = max(max_len, count)
				count = -float('inf')
				increasing = False
			last = A[i]
		if max_len < 3:
			return 0
		return max_len


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if not A or len(A) < 3:
			return 0
		left = right = mid = max_moun = 0
		while right < len(A):
			prev = mid
			while right + 1 < len(A) and A[right + 1] > A[right]:
				right += 1
				mid += 1
			if prev != mid:
				while right + 1 < len(A) and A[right + 1] < A[right]:
					right += 1
				if mid != 0 and mid != len(A) - 1:
					max_moun = max(max_moun, right - left + 1)
			right = mid + 1
			left = right
			mid = right
		if max_moun < 3:
			return 0
		return max_moun


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		left = right = 0
		max_length = 0
		while left < len(A):
			prev = A[left]
			climbing = False
			descending = False
			right = left + 1
			while right < len(A):
				current = A[right]
				if prev < current and (not descending):
					climbing = True
				elif prev > current and (climbing or descending):
					climbing = False
					descending = True
				else:
					right -= 1
					break
				right += 1
				prev = current
			if right == len(A):
				right -= 1
			curr_length = right - left + 1
			if curr_length > 2 and descending:
				max_length = max(max_length, curr_length)
			left = max(left + 1, right)
		return max_length


class Solution:

	def mountain_search(self, start, A):
		valid_mountain = True
		i = start
		while i < len(A) - 1 and A[i] < A[i + 1]:
			i += 1
		if i < len(A) - 1 and A[i] != A[i + 1]:
			while i < len(A) - 1 and A[i] > A[i + 1]:
				i += 1
		else:
			valid_mountain = False
		return (valid_mountain, i)

	def longestMountain(self, A: List[int]) -> int:
		max_mountain = 0
		i = 0
		if not A:
			return 0
		A.append(A[-1] + 1)
		while i < len(A) - 3:
			if A[i] < A[i + 1]:
				(valid, new_i) = self.mountain_search(i, A)
				if valid:
					max_mountain = max(max_mountain, new_i - i + 1)
				i = new_i
			else:
				i += 1
		return max_mountain


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		res = 0
		for i in range(1, len(A) - 1):
			if A[i + 1] < A[i] > A[i - 1]:
				l = r = i
				while l and A[l] > A[l - 1]:
					l -= 1
				while r + 1 < len(A) and A[r] > A[r + 1]:
					r += 1
				if r - l + 1 > res:
					res = r - l + 1
		return res


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		is_peak = False
		index = 1
		longest = 0
		while index < len(A) - 1:
			if A[index] > A[index - 1] and A[index] > A[index + 1]:
				is_peak = True
			if not is_peak:
				index += 1
				continue
			left = index - 1
			while left - 1 >= 0 and A[left] > A[left - 1]:
				left -= 1
			right = index + 1
			while right + 1 < len(A) and A[right] > A[right + 1]:
				right += 1
			longest = max(longest, right - left + 1)
			index = right
			is_peak = False
		return longest


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		up = down = ans = 0
		for i in range(1, len(A)):
			if A[i - 1] == A[i]:
				up = down = 0
			elif A[i - 1] < A[i]:
				if down or up == 0:
					up = 2
					down = 0
				else:
					up += 1
			else:
				down += 1
			if up and down:
				ans = max(ans, up + down)
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		res = cur = 1
		desc = False
		for i in range(1, len(A)):
			if A[i - 1] == A[i]:
				if desc:
					res = max(res, cur)
				desc = False
				cur = 1
			elif A[i - 1] < A[i]:
				if not desc:
					cur += 1
				else:
					res = max(res, cur)
					cur = 2
					desc = False
			elif desc:
				cur += 1
			elif cur > 1:
				desc = True
				cur += 1
			else:
				cur = 1
				desc = False
		if desc:
			res = max(res, cur)
		return 0 if res < 3 and (not desc) else res


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		res = 0
		i = 0
		while i < len(A):
			j = i
			while j + 1 < len(A) and A[j] < A[j + 1]:
				j += 1
			mid = j
			while j + 1 < len(A) and A[j] > A[j + 1]:
				j += 1
			if i < mid < j:
				res = max(res, j - i + 1)
			if i == j:
				i += 1
			else:
				i = j
		return res


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		long_mont = 0
		(i, j) = (0, 0)
		while j < len(A):
			incr = False
			while j != len(A) - 1 and A[j] < A[j + 1]:
				incr = True
				j += 1
			if not incr:
				j += 1
				i = j
				continue
			decr = False
			while j != len(A) - 1 and A[j] > A[j + 1]:
				decr = True
				j += 1
			if not decr:
				j += 1
				i = j
				continue
			curr_len = j - i + 1
			if curr_len >= 3:
				long_mont = max(long_mont, curr_len)
			i = j
		return long_mont


class Solution(object):

	def longestMountain(self, A):
		N = len(A)
		ans = base = 0
		while base < N:
			end = base
			if end + 1 < N and A[end] < A[end + 1]:
				while end + 1 < N and A[end] < A[end + 1]:
					end += 1
				if end + 1 < N and A[end] > A[end + 1]:
					while end + 1 < N and A[end] > A[end + 1]:
						end += 1
					ans = max(ans, end - base + 1)
			base = max(end, base + 1)
		return ans


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		(longest, i) = (0, 1)
		while i < len(A) - 1:
			is_peak = A[i - 1] < A[i] and A[i] > A[i + 1]
			if is_peak:
				left = i - 2
				while left >= 0 and A[left] < A[left + 1]:
					left -= 1
				right = i + 2
				while right < len(A) and A[right] < A[right - 1]:
					right += 1
				longest = max(longest, right - left - 1)
				i = right
			else:
				i += 1
				continue
		return longest


class Solution:

	def longestMountain(self, A: List[int]) -> int:
		if len(A) < 3:
			return 0
		a = A
		start = 0
		end = 0
		maxlen = 0
		n = len(a)
		while start < n - 1 and end < n:
			end = start
			if a[start] < a[start + 1]:
				while end < n - 1 and a[end] < a[end + 1]:
					end += 1
				if end < n - 1 and a[end] > a[end + 1]:
					while end < n - 1 and a[end] > a[end + 1]:
						end += 1
					maxlen = max(maxlen, end - start + 1)
			start = max(start + 1, end)
		return maxlen