0

谁能帮我解决这个我一直试图解决的问题。

假设有一个数字数组 A[1,2...n]，我们希望使用 Divide an Conquer 方法找到最长的递增连续子序列。具体来说，我们希望找到索引 i,j 使得 i<=j 和 A[i]<=A[i+1]<=.....A[j]。例如，如果数组有 4,1,3,5,6,7,5,8,2 那么它必须返回 [1,3,5,6,7]。

我已经对这个问题进行了很多搜索，但我能找到的只是动态方法和没有连续元素的最长增加子序列。

4

2 回答 2

1

这个怎么样：

  1. 将数组 A 划分为 A1 和 A2。

  2. 求子数组A1、A2的最长连续子序列，分别命名为s1、s2。

  3. 如果最长的连续子序列穿过 A1 和 A2，则连续子序列必须使用 A1 的最后一个和 A2 的第一个，命名为 s3。

  4. 比较 s1, s2, s3，找出最长的。

  5. 在第 2 步中，需要不断地划分子数组。第 3 步和第 4 步是征服过程。

于 2016-03-14T03:34:46.857 回答
1

一个分而治之的解决方案可以通过将数组分成 2 来完成，比如 A 1和 A 2。然后，一旦递归地解决了两个子数组的问题，您应该考虑原始数组的最优解可能所在的场景。

选项 1：最长的连续递增子序列完全在 A 1中，在这种情况下，您已经找到了最大长度，或相关答案，或者您打算返回的任何内容。

选项2：同样，最长的连续递增子序列完全在A 2中。

选项3：最长的连续递增子序列部分在A 1中，部分在Array 2中。在这种情况下，考虑到 A 1是数组的左侧部分并且 A 2是右侧部分，您基本上必须从交叉点向左走，直到它不减少或到达 A 1的左端。然后你在 A 2上向右走，直到它没有增加或者你到达它的右端。

在这些选项中，您选择长度最长的一个，您就完成了。

但是，我应该注意，分而治之并不是这个问题的最佳解决方案，因为它具有O(nlogn)时间复杂度。正如 Jon Bentley 的著名著作Programming Pearls中所提到的，他称之为最大和连续子序列问题的解决方案已知具有线性时间复杂度。该解决方案可以很容易地适应处理增加的子序列，而不是最大和。

该算法基于 Bentley 称为扫描的方法，并且基于任何子序列必须在某个点结束的想法。

该方法非常简单，可以在下面找到 Python 实现。

def maxIncreasing(arr):
    maxLength = 1
    maxStart = 0
    curStart = 0
    curLength = 1
    for i in range(1, len(arr)):
        if arr[i] <= arr[i-1]:
            if curLength > maxLength:
                maxLength = curLength
                maxStart = curStart
            curStart = i
            curLength = 1
        else:
            curLength += 1
    if curLength > maxLength:
        maxLength = curLength
        maxStart = curStart
    return (maxLength, maxStart)
于 2016-03-14T09:08:03.750 回答