Возврат длиннейшего подмассива Wiggle - PullRequest
Новая
       31

Возврат длиннейшего подмассива Wiggle

1 голос
/ 08 ноября 2019

При наличии массива чисел (или в данном случае серии панд) возвращается самый длинный подрешеток покачивания. Массив покачивания таков, что числа чередуются по направлению - они идут строго вверх и вниз. Т.е. 

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

1 Ответ

1 голос
/ 08 ноября 2019

Вы можете реализовать жадное решение, которое имеет линейную сложность, итерируя и проверяя условие зигзаг , жадно беря элементы, пока не достигнете элемента, который нарушает условие, затем вы максимизируете ответ (диапазон, который вы ужеиметь, который не нарушает условие) и повторить операцию, начиная с текущего элемента (того, который нарушил условие).

Это работает, потому что если элемент нарушает условие, то нет лучшего ответа, включая диапазон до этого элемента и после него.

Я не на своей машине, чтобы запуститькод, но вот пример (следуйте за комментариями): 

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]
...