递归，分而治之算法，用于最长的非减少数字数组

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

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”

任何帮助不胜感激。

谢谢

来源

2011-10-11 John Smith

遍历列表，并选择“分割点”，以发生减少的地方。然而，除非你在中间选择一个分割点，否则这不会真正“分裂”。我会从中间开始，然后向外迭代。以i = m（中）然后m-1，m + 1，m-2，m + 2等循环，直到i和i + 1之间的减小。然后将阵列切成两半，然后在每一半上进行递归。如果不存在减少，则返回序列的长度。 – VoidStar

你确定子阵列需要由连续的元素组成吗？这个问题得到了子序列的方式更有趣......

无论如何，如果你需要一分而治之算法尽量遵循的基本蓝图：

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应回来帮助你。您将需要处理增加的子阵列位于其中一个半边的情况以及跨越边界的情况。

来源

2011-10-11 00:30:18 hugomg

其他答案是一个很好的通用答案。

但是，我将建议关键是要知道在结果结合时需要回答哪些问题。如果结果1代表阵列[I，J]和结果2代表[J + 1，K]那么这些都是你需要能够回答的问题：

什么是最长的非递减序列两端在j？
什么是从j + 1开始的最长非递减序列？
到目前为止，我所看到的最大长度序列是什么（包括以j结尾并从j + 1开始的序列）？

如果你认为你已经可以回答这些问题对RESULT1和RESULT2，那么你应该能够确定答案为合并后的结果[I，K]（即最长始于我，和最长的序列开始于k，以及迄今为止您所见过的最长的那两个）。

来源

2011-11-10 23:50:15 Nate

递归，分而治之算法，用于最长的非减少数字数组

回答

相关问题