使用递归在数组中寻找最大值

Question

对于我被要求解决的问题之一，我找到了使用for循环的数组的最大值，所以我试图用递归找到它，这就是我想出来的搭配：

public static int findMax(int[] a, int head, int last) { 

    int max = 0; 
    if (head == last) { 
     return a[head]; 
    } else if (a[head] < a[last]) { 
     return findMax(a, head + 1, last); 
    } else { 
     return a[head]; 
    } 
} 

所以它工作正常，并获得最大的价值，但我的问题是：这是确定有基础方案返回[主治]和的情况下，在头部值是>最后的价值？

Answer 1

你可以很容易地只用一个计数器，要比较这个时间值的只是指数做到这一点：

public static int findMax(int[] a, int index) { 
    if (index > 0) { 
     return Math.max(a[index], findMax(a, index-1)) 
    } else { 
     return a[0]; 
    } 
} 

这更好的节目是怎么回事，并使用默认“递归“布局，例如与共同的基础步骤。最初的呼叫是通过做findMax(a, a.length-1)。

Answer 2

它实际上比这更简单。基本情况是，如果你已经到达数组的末尾（下面的三元控制块的'else'部分）。否则，您将返回当前和递归调用的最大值。

public static int findMax(int[] a) { 
    return findMax(a, 0); 
} 
private static int findMax(int[] a, int i) { 
    return i < a.length 
      ? Math.max(a[i], findMax(a, i + 1)) 
      : Integer.MIN_VALUE; 
} 

在每个元素处，您返回当前元素中的较大值以及具有较大索引值的所有元素。将仅在空数组上返回Integer.MIN_VALUE。这是以线性时间运行的。

Answer 3

我会通过在每次递归调用时将数组分成一半来解决这个问题。

findMax(int[] data, int a, int b) 

其中a和b是数组索引。

停止条件是当b - a <= 1，那么它们是邻居，最大值是max（a，b）;

初始呼叫：

findMax(int[] data, int 0, data.length -1); 

这降低从N个最大递归深度到log2（N）。
但是搜索工作仍然停留在O（N）。

这将导致

int findMax(int[] data, int a, int b) { 
    if (b - a <= 1) { 
    return Math.max(data[a], data[b]); 
    } else { 
    int mid = (a+b) /2; // this can overflow for values near Integer.Max: can be solved by a + (b-a)/2; 
    int leftMax = findMax(a, mid); 
    int rightMax = findMax(mid +1, b); 
    return Math.max(leftMax, rightMax); 
    } 
} 

Answer 4

int maximum = getMaxValue (arr[arr.length - 1 ], arr, arr.length - 1); 

public static int getMaxValue (int max, int arr[], int index) 
{ 
    if (index < 0) 
     return max; 
    if (max < arr[index]) 
     max = arr[index]; 
    return getMaxValue (max, arr, index - 1); 
} 

我觉得，使用跟踪器电流最大值将是一件好事。

Answer 5

您可以按照如下递归方式进行操作。

经常性的关系就像这样。

f(a,n) = a[n] if n == size 
      = f(a,n+1) if n != size 

执行如下。

private static int getMaxRecursive(int[] arr,int pos) { 
     if(pos == (arr.length-1)) { 
       return arr[pos]; 
     } else {   
       return Math.max(arr[pos], getMaxRecursive(arr, pos+1)); 
     } 
    } 

和呼叫看起来像这样

 int maxElement = getMaxRecursive(arr,0); 

Answer 6

这件怎么样？

public static int maxElement(int[] a, int index, int max) { 
    int largest = max; 
    while (index < a.length-1) { 
     //If current is the first element then override largest 
     if (index == 0) { 
      largest = a[0]; 
     } 
     if (largest < a[index+1]) { 
      largest = a[index+1]; 
      System.out.println("New Largest : " + largest); //Just to track the change in largest value 
     } 
     maxElement(a,index+1,largest); 
    } 
    return largest; 
} 

Answer 7

我知道它的旧线程，但也许这有助于！

public static int max(int[] a, int n) { 
     if(n < 0) { 
      return Integer.MIN_VALUE; 
     } 
     return Math.max(a[n-1], max(a, n - 2)); 

    } 

Answer 8

我遇到了这个线程，它帮了我很多。附加是我在递归和除法&征服案件中的完整代码。 除法&征服的运行时间比递归略好。

//use divide and conquer. 
public int findMaxDivideConquer(int[] arr){ 
    return findMaxDivideConquerHelper(arr, 0, arr.length-1); 
} 
private int findMaxDivideConquerHelper(int[] arr, int start, int end){ 
    //base case 
    if(end - start <= 1) return Math.max(arr[start], arr[end]); 
    //divide 
    int mid = start + (end - start)/2; 
    int leftMax =findMaxDivideConquerHelper(arr, start, mid); 
    int rightMax =findMaxDivideConquerHelper(arr, mid+1, end); 
    //conquer 
    return Math.max(leftMax, rightMax); 
} 

// use recursion. return the max of the current and recursive call 
public int findMaxRec(int[] arr){ 
    return findMaxRec(arr, 0); 
} 
private int findMaxRec(int[] arr, int i){ 
    if (i == arr.length) { 
     return Integer.MIN_VALUE; 
    } 
    return Math.max(arr[i], findMaxRec(arr, i+1)); 
} 

Answer 9

class Test 
{ 
    int high; 
    int arr[]; 
    int n; 
    Test() 
    { 
     n=5; 
     arr = new int[n]; 
     arr[0] = 10; 
     arr[1] = 20; 
     arr[2] = 30; 
     arr[3] = 40; 
     arr[4] = 50; 
     high = arr[0]; 
    } 
    public static void main(String[] args) 
    { 
     Test t = new Test(); 
     t.findHigh(0); 
     t.printHigh(); 
    } 
    public void printHigh() 
    { 
     System.out.println("highest = "+high); 
    } 
    public void findHigh(int i) 
    { 
     if(i > n-1) 
     { 
      return; 
     } 
     if(arr[i] > high) 
     { 
      high = arr[i]; 
     } 
     findHigh(i+1); 
     return; 
    } 
} 

Answer 10

其不好吧！ 您的代码将无法找到数组中的最大元素，它只会返回具有比其旁边元素更高值的元素，为了解决此问题，可以将范围中的最大值元素作为参数传递给递归方法。

private static int findMax(int[] a, int head, int last,int max) { 
    if(last == head) { 
     return max; 
    } 
    else if (a[head] > a[last]) { 
      max = a[head]; 
      return findMax(a, head, last - 1, max); 
     } else { 
      max = a[last]; 
      return findMax(a, head + 1, last, max); 
     } 
}