最长山脉

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/f4e974a50eda429fbf36515a4197b148?tpId=196&tqId=40556&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        left[i]表示以下标i结尾的连续递增子数组的长度，right[i]表示以下标i开头的连续递减子数组的长度。
        初始化：
            left[0] = 1
            right[-1] = 1
        状态转移方程：
            left[i] = left[i - 1] + 1 if nums[i] > nums[i - 1] else 1
            right[i] = right[i + 1] + 1 if nums[i] > nums[i + 1] else 1
        遍历下标1 ~ n - 2，：
            m = left[i] + right[i] - 1
            如果山脉长度m大于等于3，更新res
        找不到山脉，则返回0
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def longestmountain(self, nums):
        # write code here
        n = len(nums)

        left, right = [1] * n, [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                left[i] = left[i - 1] + 1
        for j in range(n - 2, -1, -1):
            if nums[j] > nums[j + 1]:
                right[j] = right[j + 1] + 1

        res = 0
        for i in range(1, n - 1):
            m = left[i] + right[i] - 1
            if m >= 3:
                res = max(res, m)
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums = [2, 5, 2, 1, 5]

    nums = [2, 2, 2, 2, 1]

    res = sol.longestmountain(nums)

    print res