递归获得数组中的最大差异

返回数组中的一对数字p和q。 p必须阵列q中之前出现，和QP必须是可能的最高值递归获得数组中的最大差异

A = [1,4,12,5,9,1,3,8]

返回值将会是p = 1 & q = 12

有人建议下面的解决方案。但是我不知道它应该在“第三案”返回的建议如下：

建议：

分A在A1均匀地分成两个较小的排列A1，A2，并解决问题（递归）和A2。这可以帮助你找到最佳的A吗？不要忘记你可以使用额外的处理，花费高达O（n）。假设p，q是A的最优对。p，q∈A1或p，q∈A2，或者都不是案件属实。在第三种情况下，你可以说p和q？

下面是我的代码，它基本上将数组分开，并从前半部分获得最小值，从后半部分获得最大值。有0（n）的解决方案，但我对递归有兴趣，因为我正在学习递归。所以请不要建议任何其他解决方案。

#define min_f(a, b) (a)>(b)?(b):(a) 
    #define max_f(a, b) (a)>(b)?(a):(b) 
    #define MAX 1 << 30 
    #define MIN -1 

    int get_min(int *a, int start, int end) 
    { 
      int t_min = MAX; 
      while(start <= end) { 
        t_min = min_f(t_min, a[start]); 
        start++; 
      } 
      return t_min; 
    } 

    int get_max(int *a, int start, int end) 
    { 
      int t_max = MIN; 
      while(start <= end) { 
        t_max = max_f(t_max, a[start]); 
        start++; 
      } 
      return t_max; 
    } 

    int foo(int *a, int start, int end) 
    { 
      int g_max = MIN; 
      int min, max, i; 

      for(i=0;i<=end;i++) { 
        min = get_min(a, start, i); 
        max = get_max(a, i+1, end); 
        if (max > min) { 
          g_max = max_f(g_max, max-min); 
        } 
      } 
      return g_max; 
    } 

    int main() 
    { 
      int a[] = {1,4,12,5,9,1,3,8}; 
      int size = sizeof(a)/sizeof(a[0]); 
      printf("%d\n", foo(a, 0, size-1)); 
      return 0; 
    }

来源

2015-06-20 newbie_old

闻起来像功课。 – mikeb

@mikeb：你为什么这么想？我真的不喜欢那些不问问题的人，并假设（你和我）。 http://cs.stackexchange.com/questions/14665/create-divide-and-conquer-algorithm/14668#14668 –

不，我不会删除它，因为即使它不是“家庭作业”，你应该尝试当你陷入困境时，自己想办法来到这里。你来这里试图让某人为你做，而不是至少做出努力。采取刺解决方案，我不仅会删除-1，我会帮你解决它。如果这个问题太难了，也许你应该解决一些简单的问题，比如一个函数采用n来返回斐波那契（n）。这是一个经典的递归问题，应该让你开始。 – mikeb

你的递归解决方案不过是一个Divide and Conquer algorithm.您也可以查找Binary-search algorithm理解分而治之的基本概念。

现在，让我们以你为例。

    [1,4,12,5,9,1,3,8] 
         /\ 
        /\ 
        / \ 
      [1,4,12,5] [9,1,3,8]

如果你读过上面的链接，或者你知道分而治之算法，你就会明白，我们做递归操作左子数组和右子数组。下一步是，我们再次分割每一半。在这里，让我们来做一下前半部分，到达第三个案例就足够了，这是你无法理解的。

拿上半场，再划分一次。

    [1,4,12,5] 
        /\ 
        /\ 
       / \ 
       [1,4]  [12,5]

在这个分割数组的步骤中，您应该已经理解了第三种情况。答案p = 1（左半部分）和q = 12（右半部分）位于分歧后的不同半部分

这是第三种情况。现在，我把它留给你写这个递归代码，并在代码中适当地处理第三种情况。

来源

2015-06-20 13:25:30

递归获得数组中的最大差异

回答

相关问题