LeetCode-Solutions/Python/longest-alternating-subarray-after-removing-at-most-one-element.py at master · kamyu104/LeetCode-Solutions · 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
# Time:  O(n)
# Space: O(1)

# dp
class Solution(object):
    def longestAlternating(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = up1 = up0 = down1 = down0 = 1
        for i in range(len(nums)-1):
            if nums[i] < nums[i+1]:
                up1, up0, down1, down0 = down1+1, down0+1, down0, 1
            elif nums[i] > nums[i+1]:
                up1, up0, down1, down0 = up0, 1, up1+1, up0+1
            else:
                up1, up0, down1, down0 = up0, 1, down0, 1
            result = max(result, up1, down1)
        return result


# Time:  O(n)
# Space: O(n)
# prefix sum
class Solution2(object):
    def longestAlternating(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = [1]*len(nums)
        for i in xrange(1, len(nums)):
            diff = cmp(nums[i-1], nums[i])
            if not diff:
                continue
            left[i] = left[i-1]+1 if i-2 >= 0 and cmp(nums[i-2], nums[i-1]) == -diff else 2
        right = [1]*len(nums)
        for i in reversed(xrange(len(nums)-1)):
            diff = cmp(nums[i], nums[i+1])
            if not diff:
                continue
            right[i] = right[i+1]+1 if i+2 < len(nums) and cmp(nums[i+1], nums[i+2]) == -diff else 2
        result = max(left)
        for i in xrange(1, len(nums)-1):
            diff = cmp(nums[i-1], nums[i+1])
            if not diff:
                continue
            l = (left[i-1] if i-2 >= 0 and cmp(nums[i-2], nums[i-1]) == -diff else 1)
            r = (right[i+1] if i+2 < len(nums) and cmp(nums[i+1], nums[i+2]) == -diff else 1)
            result = max(result, l+r)
        return result