algorithm - 最长非递减数组的递归分而治之算法

Question

对于这个问题，我遇到了一些严重的问题。我需要一个“分而治之”的递归算法，告诉我最长的非递减数字数组的长度。就个人而言，我会选择使用我在仔细阅读问题之前编写的这段代码。

 int bestIndex = 0;
    int bestLength = 0;
    int curIndex = 0;
    int curLength = 1;

    for (int i = 1; i < a.length; i ++){
        if (a[i] >= a[i-1]){
            curLength ++;
        }else {
            curLength = 1;
            curIndex = i;
        }
        if (curLength > bestLength){
            bestIndex = curIndex;
            bestLength = curLength;
        }
    }
    return bestLength;

问题是作业要求我使用分而治之的方法，我想不出一种方法来做到这一点。

例如“4 2 3 3 1 2 4 5 9 2”它会返回“5”，因为“1 2 4 5 9”

非常感谢任何帮助。

谢谢

Answer 1

你确定子数组需要由连续的元素组成吗？对于子序列，这个问题变得更有趣...

无论如何，如果您需要分而治之的算法，请尝试遵循基本蓝图:

function f(array) =
    if array is empty or constant size or something like that
        handle base case
    else
        result1 <- f(first half of the array)
        result2 <- f(second half of the array)
        return some_way_to_combine(result1, result2)

当然，您需要正确选择 f 应返回的内容以帮助您解决问题。您将需要处理递增子数组位于其中一半内部的情况以及它越过边界的情况。