对于我被要求解决的问题之一，我使用 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];
}
}
所以它工作正常并获得最大值，但我的问题是：对于基本情况返回 a[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 + (b-a) / 2;
int leftMax = findMax(a, mid);
int rightMax = findMax(mid +1, b);
return Math.max(leftMax, rightMax);
}
}
我遇到了这个线程，它对我帮助很大。附件是我在递归和分治两种情况下的完整代码。分而治之的运行时间略好于递归。
//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;
}
}
这个如何 ？
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;
}
我知道它是一个旧线程，但也许这有帮助！
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));
}
您可以按以下方式递归地执行此操作。
循环关系是这样的。
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);
感谢@Robert Columbia 的建议！
更新： 下面的函数将从索引 0 递归开始，它将继续添加到这个索引值直到它等于数组的长度，如果它更多，我们应该停止并返回 0。一旦我们这样做了，我们需要获取数组中每两项的最大值，例如：
A = [1 , 2 , 3 ];
A[0] ( 1 ) vs A[1] ( 2 ) = 2
A[1] ( 2 ) vs A[2] ( 3 ) = 3
Max(2,3) = 3 ( The answer )
public int GetMax(int [] A, int index) {
index += 1;
if (index >= A.Length) return 0;
return Math.Max(A[index], GetMax(A, index + 1));
}
不行！您的代码不会在数组中找到最大元素，它只会返回值高于它旁边的元素的元素，为了解决这个问题，可以将范围内的最大值元素作为递归的参数传递方法。
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 class Test1 {
public static int findMax(int[] a, int head, int last) {
int max = 0, max1 = 0;
if (head == last) {
return a[head];
} else if (a[head] < a[last]) {
max = findMax(a, head + 1, last);
} else
max = findMax(a, head, last - 1);
if (max >= max1) {
max1 = max;
}
return max1;
}
public static void main(String[] args) {
int arr[] = {1001, 0, 2, 1002, 2500, 3, 1000, 7, 5, 100};
int i = findMax(arr, 0, 9);
System.out.println(i);
}
}
私有静态int getMax（int [] arr，int idx）{
if (idx==arr.length-1 ) return arr[idx];
return Math.max(arr[idx], getMax (arr,idx+1 ));
}
static int maximumOFArray(int[] array,int n) {
int max=Integer.MIN_VALUE;
if(n==1) return array[0];
else
max=maximumOFArray(array, --n);
max= max>array[n] ? max : array[n];
return max;
}
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 );
}
我觉得使用跟踪器获取当前最大值会很好。