Algorithm-LeetCode/Solutions/0978.Longest_Turbulent_Subarray.py at main · ling67/Algorithm-LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
"""
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

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

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

For i <= k < j:
arr[k] > arr[k + 1] when k is odd, and
arr[k] < arr[k + 1] when k is even.
Or, for i <= k < j:
arr[k] > arr[k + 1] when k is even, and
arr[k] < arr[k + 1] when k is odd.


Example 1:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
Example 2:

Input: arr = [4,8,12,16]
Output: 2
Example 3:

Input: arr = [100]
Output: 1


Constraints:

1 <= arr.length <= 4 * 104
0 <= arr[i] <= 109
"""

"""
1.define state:
dp_inc[i] nums[i] > nums[i-1]
dp_dec[i] nums[i] < nums[i-1]
2.get max(dp_inc[i], dp_dec[i])
3.
dp_inc[0] = 1
dp_dec[0] = 1
4.transit function
if nums[i] > nums[i-1]
dp_inc[i] = dp_dec[i-1] + 1
else:
dp_dec[i] = dp_inc[i-1] + 1
"""
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        dp_inc = [0] * n
        dp_dec = [0] * n
        dp_inc[0], dp_dec[0] = 1, 1

        for i in range(1, n):
            if arr[i] > arr[i-1]:
                dp_inc[i] = dp_dec[i-1] + 1
                dp_dec[i] = 1
            elif arr[i] < arr[i-1]:
                dp_dec[i] = dp_inc[i-1] + 1
                dp_inc[i] = 1
            else:
                dp_dec[i] = 1
                dp_inc[i] = 1

        max1 = max(dp_dec)
        max2 = max(dp_inc)

        return max1 if max1>max2 else max2

"""
1.状态定义
dph[i] 从A[i]结尾的动荡子列的最大长度， A[i]是high
dp[i] 从A[i]结尾的动荡子列的最大长度， A[i]是low
2.求 return max{i=0,....,n-1}max(dph[i], dpl[i])
3.初始化 dph[0] = dpl[0] = 1
4.递推公式
if A[i] > A[i-1], dph[i] = dpl[i-1] + 1, dpl[i] = 1
if A[i] < A[i-1], dpl[i] = dph[i-1] + 1, dph[i] = 1
if A[i] = A[i-1], dph[i] = dpl[i] = 1
"""
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        max_lens = 1
        inc, dec = 1, 1  #inc 第0个元素结尾的上一个是递增的值
        for i in range(1, len(arr)):
            if arr[i] > arr[i-1]:
                inc = dec + 1
                dec = 1
            elif arr[i] < arr[i-1]:
                dec = inc + 1
                inc = 1
            else:
                inc = 1
                dec = 1

            max_lens = max(max_lens, inc, dec)

        return max_lens