使用递归查找数组中的最大值
对于我被要求解决的一个问题，我发现使用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]; } } 因此它工作正常并获得最大值，但我的问题是：是否可以为基本情况返回[head]并且对于头部的值是>最后值的情况？
你可以只用一个计数器轻松完成它，只需要你想要比较的值的索引：
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) 。
它实际上要简单得多。 基本情况是你到达了数组的末尾（下面的三元控制块的’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仅在空数组上返回。 这在线性时间内运行。
我会通过在每次递归调用中将数组分成一半来解决这个问题。
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 + (ba) / 2; int leftMax = findMax(a, mid); int rightMax = findMax(mid +1, b); return Math.max(leftMax, rightMax); } }
这个如何 ？
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; }
我遇到了这个post，它给了我很多帮助。 附件是我在递归和分治案件中的完整代码。 分而治之的运行时间略好于递归。
//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)); }
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; } }
您可以按如下方式递归执行此操作。
经常性关系就像这样。
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);
我知道它是一个老线程，但也许这有帮助！
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)); }
它还不行！ 你的代码将找不到数组中的最大元素，它只返回值高于其旁边元素的元素，为了解决这个问题，范围中的最大值元素可以作为递归的参数传递方法。
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); } }
public int GetMax(int [] A, int index) { index += 1; if (index >= A.Length) return 0; return Math.Max(A[index], GetMax(A, index + 1)); }
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 ); }
我觉得使用跟踪器获得当前最大值会很好。