Return 最长的 Wiggle 子阵列

Question

给定一个数字数组（或在本例中为 pandas 系列）return 最长的摆动子数组。摆动数组是一种数字在方向上交替的数组——它们严格地上下移动。 IE。

Input: [10, 22, 9, 33, 49, 50, 31, 60, 15]

Output: [49, 50, 31, 60, 15]

数组必须按顺序组成，即不能跳值组成数组。

可以在下面找到我天真的蛮力方法 - 我很难让它发挥作用。有什么建议吗？

def zigzag(arr):
    result = pd.Series([])
    for i in range(len(arr)-2):
         if arr[i:i+3] != sorted(arr[i:i+3]) and arr[i:i+3] != sorted(arr[i:i+3], reverse = True): # no three points increase or decrease
            result = result.append(pd.Series(arr[i:i+3], index = list(range(i, i+3))))
            result = result.loc[~result.index.duplicated(keep='first')] 
         else:
            result = pd.Series([])
    return result

Answer 1

您可以通过迭代和检查 之字形 条件来实现具有线性复杂度的贪婪解决方案，贪婪地获取元素直到找到打破条件的元素，然后最大化回答（你已经拥有的不破坏条件的范围）并从当前元素（破坏条件的元素）开始重复操作。

这是可行的，因为如果一个元素打破了条件，那么就没有更好的答案，包括该元素之前和之后的范围。

我不在我的机器上运行代码，但这里有一个例子（按照评论）：

def zigzag(arr):
    mx, cur, lst, op = 0, 0, -1, 0
    st, en = 0, 0
    ans = 0
    for i, x in enumerate(arr):
        # if its the first element we take it greedily
        if lst == -1:
            lst = x
            st = i
        # else if lst is the first element taken then decide which direction we need next
        elif op == 0:
            if x > lst:
                op = 1
            elif x < lst:
                op = -1
            # if current element is equal to last taken element we stop and start counting from this element
            else:
                # check if current range is better than previously taken one
                if i-st > mx:
                    mx = i-st
                    ans = st
                    en = i
                st = i
                op = 0

            lst = x
        else:
            # if direction meets the inequality take the current element
            if (op == 1 and x < lst) or (op == -1 and x > lst):
                op *= -1
                lst = x
            # otherwise, check if the current range is better than the previously taken one
            else:
                if i-st > mx:
                    mx = i-st
                    ans = st
                    en = i
                st = i
                lst = x
                op = 0
    # if starting index is greater than or equal to the last, then we have reached the end without checking for maximum range
    if st >= en:
        if len(arr)-st > en-ans:
            ans = st
            en = len(arr)
    result = [arr[i] for i in range(ans, en)]
    return result

print(zigzag([10, 22, 9, 33, 49, 50, 31, 60, 15]))
# [49, 50, 31, 60, 15]

Return 最长的 Wiggle 子阵列

Return Longest Wiggle Subarray

python

arrays

dynamic-programming

greedy

zigzag