Leetcode 978. Longest Turbulent Subarray (Python)

Related Topic

Dynamic-Programming.

Description

A subarray A[i], A[i+1], …, A[j] of A is said to be turbulent if and only if:

• For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
• OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Sample I/O

Example 1

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2

Input: [4,8,12,16]
Output: 2

Example 3

Input: [100]
Output: 1

Note:

• 1 <= A.length <= 40000
• 0 <= A[i] <= 10^9

Methodology

This question can be solved by Dynamic Programming. It is similar with question 646. Maximum Length of Pair Chain. But now, the question is asking how many numbers of the longest increasing subsequence.

The question is intentionally confused. In face, You can translate For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even; OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd. to find the longest sequence that in every three consective numbers, the middle number is either greater than others or smaller than others.

Find the base case:

If there is only 1 element, then we return 1. Otherwise, we init the first element as 1, others are 2 because for the first element, the length of sequence can only be 1, for others, the length of sequence can at least be 2

Find the pattern:

If the current element is greater than previous, then we need next to be smaller. If the current element is smaller than previous, then we need next to be greater. If the current element is equal to the previous, then we need make the current as a new start which is 1.

Answer:

Return the maxmium value from dp list as maxmium value here is the longest length

Code

def maxTurbulenceSize(self, A: List[int]) -> int:
        size = len(A)
        dp=[2]*size
        dp[0]=1
        if size < 2: return 1
        flag = 1 if A[1]>A[0] else 0 #1: need smaller and 0: need bigger
        for i in range(1, size):
            if A[i]==A[i-1]:
                dp[i]=1
                continue
            if flag and A[i]<A[i-1]:
                dp[i]=dp[i-1]+1
                flag = 0
            elif not flag and A[i]>A[i-1]:
                dp[i]=dp[i-1]+1
                flag = 1
        return max(dp)

BigO

Create dp list will cost O(n) and iterate the dp will cost ((n-1)) in total will be O(2n-1)