問題描述

Given an array of numbers, find the longest alternating subsequence. That is, a subsequence [a1, a2, a3, ..., ak] where a1>a2, a2< a3,a3>a4 ..., or vice versa (graphically looks like / \ / \ / ... or \ / \ / \ /...) .
給出一個數(shù)組，找到最長的交替子序列，即其元素的大小關(guān)系不斷交替。子序列不用連續(xù)。在英文中，一般subarray是連續(xù)的子序列，subsequence是可以不必連續(xù)的子序列。參考Geeksforgeeks的定義：

• A subbarray is a contiguous part of array.
• A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.

例如[1,2,3,4]，[1,2,3]是subarray也是subsequence，但是[1,3]只是subsequence。

詢問補充

無

思路闡述

暴力破解

暴力破解方法就是找出所有子序列，然后從長到短找到符合要求的。因為生成所有子序列的時間復(fù)雜度是O(n*2^{n)，然后判斷也需要O(n)，總共就是O((n}2)*2^n)。

如何改進

暴力破解方法明顯效率太低，一個原因就是對于已經(jīng)違反規(guī)律的開頭還會繼續(xù)生成子序列。
因此我們可以在生成子序列的過程中加入檢查，或者是針對規(guī)律來生成子序列。

DFS解法

對兩個規(guī)律可以分別求最大子序列然后再取最大值。
對于一個規(guī)律，可以采用DFS，從左往右，每次取符合規(guī)律的數(shù)，之后遞歸剩下的部分。
因為兩個規(guī)律其實很相似，可以用一個參數(shù)來控制是取大于還是小于上一個數(shù)，這樣可以共用一個遞歸函數(shù)。
由于要的是最大長度，整個遞歸時間復(fù)雜度仍然非常高：假設(shè)給出的序列就是符合要求的序列，每次遞歸都得把剩下的所有元素遞歸一遍。可以稍微改進一下，就是記錄找到的最長的序列，假如某個遞歸分支已經(jīng)不能比之更長的時候，就放棄該分支。

DP解法

兩個規(guī)律有明顯的關(guān)系，可以考慮使用DP。
假設(shè)有兩個DP數(shù)組，fall[i]和rise[i]，代表以數(shù)組A的A[i]結(jié)尾的最大fall或者rise序列長度，那么自然可以得到遞推公式：對于fall[i+1]，就找到A數(shù)組A[i+1]之前比A[i+1]大的元素k，使得rise[k+1]最大；rise同理。這樣復(fù)雜度是O（n^2）。

代碼

import copy
class Solution:
    # recursion solution
    def getLongestAlternatingSubsequence(self, A):
        if not A:
            return 0
        if len(A) == 1:
            return 1
        self.ret = 0
        self.seq = []
        self.recur(A[1:], True, 1, [A[0]])
        self.recur(A[1:], False, 1, [A[0]])
        return self.seq

    def recur(self, A, f, curL, curSeq):
        if curL > self.ret:
            self.seq = copy.deepcopy(curSeq)
            self.ret = max(self.ret, curL)
        if not A:
            return
        if curL + len(A) <= self.ret:
            return
        for i in range(len(A)):
            if f:
                # f: find rise
                if A[i] > curSeq[-1]:
                    curSeq.append(A[i])
                    self.recur(A[i + 1:], False, curL + 1, list(curSeq))
                    curSeq.pop()
            else:
                if A[i] < curSeq[-1]:
                    curSeq.append(A[i])
                    self.recur(A[i + 1:], True, curL + 1, list(curSeq))
                    curSeq.pop()

    # DP solution
    def getLongestAlternatingSubsequenceDP(self, A):
        if not A:
            return 0
        if len(A) == 1:
            return 1
        dpRiseEnd = [0] * len(A)
        dpFallEnd = [0] * len(A)
        backTrackRise = [[A[0]] for _ in range(len(A))]
        backTrackFall = [[A[0]] for _ in range(len(A))]
        dpFallEnd[0] = dpRiseEnd[0] = 1
        for i in range(1, len(A)):
            for j in range(i):
                if A[j] < A[i]:
                    if dpFallEnd[j] + 1 > dpRiseEnd[i]:
                        backTrackFall[j].append(A[i])
                        backTrackRise[i] = copy.deepcopy(backTrackFall[j])
                        backTrackFall[j].pop()
                    dpRiseEnd[i] = max(dpRiseEnd[i], dpFallEnd[j] + 1)
                if A[j] > A[i]:
                    if dpRiseEnd[j] + 1 > dpFallEnd[i]:
                        backTrackRise[j].append(A[i])
                        backTrackFall[i] = copy.deepcopy(backTrackRise[j])
                        backTrackRise[j].pop()
                    dpFallEnd[i] = max(dpFallEnd[i], dpRiseEnd[j] + 1)
        return backTrackRise[-1] if len(backTrackRise[-1]) >= len(backTrackFall[-1]) else backTrackFall[-1]

個人更推薦DP解法。由于要求得到序列，所以需要存儲節(jié)點，否則DP代碼會更加簡單。DP的時間和空間復(fù)雜度都是O(n^2)。因為后面的DP值依賴前面所有的DP值，因此不能使用滾動DP來節(jié)約空間。
可以看到我默認以A[0]為開始。這是因為，對于后面的最長交替序列，無論是以/開始還是以\開始，無論A[0]和A[1]A[2]的大小關(guān)系如何，都不影響最終結(jié)果，稍微畫個圖就知道了，把A[0]看做一個點'.'：

• 假設(shè).在/下方或者中央，那么.可以代替A[1]；
• 假設(shè).在/上方，那么可以加入組成更長的交替序列。

也就是說，一個序列的最大交替序列總是大于或者等于其子序列的交替子序列。所以，可以默認以A[0]為開頭。

總結(jié)

DP-backTrack問題。難度hard。