0

给定两个数字数组，如何通过交替两个数组的元素来找到最长的递增子序列？例如

A = [4, 1, 10, 5, 9]
B = [4, 5, 7, 14]
so the output must be [1,4,5,7,9,14]

它必须采用 a 的元素、b 的元素、a 的元素、b 的元素……的格式。

我试图找到一个解决方案，但我想不出任何东西，我尝试了 LIS 方法，但由于该代码只需要一个数组，这对我来说没有意义，对不起

（以防万一，为了更清楚 = [ 1(A), 4(B), 5(A), 7(B), 9(A), 14(B)] 也请注意顺序不能已更改）谢谢，如果我措辞不正确，请见谅

4

3 回答 3

0

最简单的方法就是这样做：

# lias: Longest Increasing Alternating Subsequence
def lias(curr, next, seq):
    good, elem = False, None
    while not good:
        if not curr: return seq
        elem = min(curr); curr.remove(elem)
        good = False if elem in seq or elem < max(seq, default=0) else True
    seq.append(elem)
    return lias(next, curr, seq)


if __name__ == '__main__':
    A = [4, 1, 10, 5, 9]
    B = [4, 5, 7, 14]
    print(lias(A,B, []))
于 2021-03-11T21:25:19.843 回答
0

您可以定义一个递归解决方案，该解决方案基于前一个元素和它来自的列表的其余元素，一次构建一个元素的序列。每个递归都可以交换参数顺序，以便逻辑只需要关心其中一个列表。

这可以通过携带基于迄今为止发现的最长序列的长度目标来进一步优化。

例如：

def longAltSeq(A,B,prev=None,minLen=0):
    result = longAltSeq(B,A,min(B)-1) if prev is None else [] # inverted params
    for i,a in enumerate(A): # Start with an item from A
        if prev is not None and a<=prev: continue     # increasing from previous
        if 2*min(len(A)-i,len(B)+1)<minLen: break     # not enough items left
        seq = [a]+longAltSeq(B,A[i+1:],a,len(result)) # alternate A<->B
        if len(seq)>len(result): result = seq         # track longest
    return result

输出：

A = [4, 1, 10, 5, 9]
B = [4, 5, 7, 14]
print(longAltSeq(A,B))
[1, 4, 5, 7, 9, 14]

解决方案从反转参数开始，因此列表的初始顺序无关紧要

于 2021-03-11T23:00:46.583 回答
-1

Here's a solution in JavaScript that'll work. You should be able to replicate that logic in Python or whatever language you need. Cheers, and welcome to the community!

var A = [4, 1, 10, 5, 9];
var B = [4, 5, 7, 14];

run(A,B);

function getSmallest(list, limit){
    var results = [];
    list.forEach(number => {
    if (number > limit)
        results.push(number);
    });
    results.sort(function(a, b) {
        return a - b;
    });
  return results[0];
}

function run(list_a,list_b){
    var result = [];
    var current_list = 1;
    var current_limit = Number.NEGATIVE_INFINITY;
    
    while (current_limit != undefined) {
        current_limit = getSmallest((current_list) ? list_a : list_b, current_limit);
        current_list = !current_list;
        result.push(current_limit);
    }

    result.pop();
    console.log(result);
}
于 2021-03-11T21:08:01.687 回答