1

我的任务是用递归动态编程方法解决交替子字符串问题：

考虑一个整数序列 A = a1, a2, a3, ... an。a 的子序列 B 是一个序列 B = b1, b2, .... ,bn，它是通过删除一些元素但保持顺序从 A 创建的。给定一个整数序列 A，目标是计算 anb 交替子序列 B，即序列 b1, ... bn 使得对于 {2, 3, ... , m-1} 中的所有 i，如果 b{i- 1} < b{i} 然后 b{i} > b{i+1} 如果 b{i-1} > b{i} 然后 b{i} < b{i+1}

到目前为止，我需要检查每个递归步骤，如果我想获取元素并寻找下一个交替数字，或者我只是获取下一个数字并从两种可能的交替开始。

s index from left e end ( len(Array)) 一个数组 g(A,s) 一个函数，它得到下一个更大或更小的整数。

我的递归公式是：V(A, s, e) = max( V(A, g(A,s),e), V(A, s+1, e) ) +1

V(A, g(A,s),e) 获取元素并继续下一个交替

V(A, s+1, e) 离开元素并在下一个元素开始新序列

假设我的实现和方法是正确的，我建议将运行时间设置为 O(n^2)，因为我们需要知道每个组合。

如果没有催眠部分，它将是 O(2^n)，就像二叉树的叶子数量一样。

这个分析正确吗？可能只是对公式正确，但对代码不正确......

函数 getsmaller 和 getbigger 是 g(A,s)

A = [5,6,5,5,5,7,5,5,5,87,5]

s = 0
e = len(A)

memo_want_small = [-1] * len(A)
memo_want_bigger = [-1] * len(A)


def getsmaller(A, s):
    erg = 0
    for i in range(s, len(A)):
        if A[i] < A[s]:
            if i is not None:
                 return i   
    return -1

def getbigger(A, s):
    for i in range(s, len(A)):
        if A[i] > A[s]:
            if i is not None:
                return i      
    return -1


def wantsmall(A, s, e):
    if s == -1: # no more alternating element
        return 0
    if s == e: # base case
        return 0
    if memo_want_small[s] is not -1:
        return memo_want_small[s]

    return_V = max(wantbigger(A, getbigger(A, s), e)  , alt(A, s+1, e)) + 1
    memo_want_small[s] = return_V
    return return_V

def wantbigger(A, s, e):
    if s == -1: # no more alternating element
        return 0
    if s == e: # base case
        return 0
    if memo_want_bigger[s] is not -1:
        return memo_want_bigger[s]

    return_V = max(wantsmall(A, getsmaller(A, s), e)  , alt(A, s+1, e)) + 1
    memo_want_bigger[s] = return_V
    return return_V

def alt(A, s, e):
    if s == e: # base case
        return 0
    return max(wantsmall(A, getsmaller(A, s), e), wantbigger(A, getbigger(A, s), e)) 



print("solution: " + str(alt(A,s,e)))
4

1 回答 1

1

让我们考虑一个从 开始的序列A[i]，方向首先向上。

首先，不可能有一个更高的元素，A[j]在它的左边A[i]结束一个更长的序列，因为如果有，我们总是可以切换那个元素A[i]并最终得到一个相同长度的向上优先序列。

* Going left from A[i], up-first

     ↖
       A[j]
            ...  A[i]

其次，左边不可能有一个较低的元素，A[j]结束一个较长的向上优先序列，而中间的一个元素，A[k]高于二。A[i]A[i]

* Going left from A[i], up-first

                A[k]
            ...      ...  A[i]
     ↖
       A[j]

因此，向左看，最长的从上到下的序列结束于A[i](1) 与在左边的下一个较高元素处结束的序列相同或更长，或者 (2) 与以最低点结束的序列的长度相同任何连续的、单调递增的子数组的元素，达到A[i].

现在，考虑一个元素 ，A[r]右边第一个更高的元素，A[i]我们希望找到以它结尾的最长的向下优先序列。正如我们所展示的，A[i]该末端左侧的元素是一个先上序列，并且在计算 的结果时高于或低于A[i]已经可以考虑的值A[i]，因此它仍然是计算最长下的唯一感兴趣的单元格-第一个序列结束于A[r]（向左看）。这指向一个O(n)动态程序。

JavaScript 代码：

// Preprocess previous higher and lower elements in O(n)
// Adapted from https://www.geeksforgeeks.org/next-greater-element
function prev(A, higherOrLower) {
  function compare(a, b){
    if (higherOrLower == 'higher')
      return a < b
    else if (higherOrLower == 'lower')
      return a > b
  }
  
  let result = new Array(A.length)
  let stack = [A.length - 1]

  for (let i=A.length-2; i>=0; i--){ 
    if (!stack.length){ 
      stack.push(A[i])
      continue
    }

    while (stack.length && compare(A[ stack[stack.length-1] ], A[i]))
      result[ stack.pop() ] = i

    stack.push(i)
  }

  while (stack.length)
    result[ stack.pop() ] = -1

  return result
}

function longestAlternatingSequence(A){
  let prevHigher = prev(A, 'higher')
  let prevLower = prev(A, 'lower')
  let longestUpFirst = new Array(A.length)
  let longestDownFirst = new Array(A.length)
  let best = 1
  
  longestUpFirst[0] = 1
  longestDownFirst[0] = 1
  
  for (let i=1; i<A.length; i++){
    // Longest up-first
    longestUpFirst[i] = Math.max(
      A[i] >= A[i-1] ? longestUpFirst[i - 1] : -Infinity,
      prevHigher[i] != -1 ? longestUpFirst[ prevHigher[i] ] : -Infinity,
      prevHigher[i] != -1 ? 1 + longestDownFirst[ prevHigher[i] ] : -Infinity,
      1
    )
    
    // Longest down-first
    longestDownFirst[i] = Math.max(
      A[i] <= A[i-1] ? longestDownFirst[i - 1] : -Infinity,
      prevLower[i] != -1 ? longestDownFirst[ prevLower[i] ] : -Infinity,
      prevLower[i] != -1 ? 1 + longestUpFirst[ prevLower[i] ] : -Infinity,
      1
    )

    best = Math.max(best, longestUpFirst[i], longestDownFirst[i])
  }

  console.log(`${ longestUpFirst } (longestUpFirst)`)
  console.log(`${ longestDownFirst } (longestDownFirst)`)
  
  return best
}

var tests = [
  [5,6,5,5,5,7,5,5,5,87,5],
  [1,2,3,4,5,6,7,8],
  new Array(10).fill(null).map(_ => ~~(Math.random()*50))
]

for (let A of tests){
  console.log(JSON.stringify(A))
  console.log(longestAlternatingSequence(A))
  console.log('')
}

更新

嘿，这里有一个更简单的 O(n) 重复：https ://www.geeksforgeeks.org/longest-alternating-subsequence/

于 2019-08-18T21:16:25.970 回答