java或python中某个范围的递归max函数

Question

我从“思考java，如何像计算机科学家一样思考”中得到了这个练习。艾伦·B·唐尼：

编写一个名为maxInRange的方法，该方法采用一个整数数组和一系列索引（lowIndexandHighIndex），并在数组中找到最大值，仅考虑lowIndex和HighIndex之间的元素，包括两端。

此方法应该是递归的。如果范围的长度为1，也就是说，如果低索引==高索引，我们立即知道范围中的唯一元素必须是最大值。这就是基本情况。

如果范围中有多个元素，我们可以将数组分成两部分，在每个部分中找到最大值，然后找到最大值的最大值。

我用python给出了一个接近但非常不准确的答案：

cycles=0

def max_in_range(lst,low,high):

    '''

    Could not be able to make it work correctly

    '''



    global cycles

    cycles+=1

    if low==high:

        #print "Cycles: ",cycles

        return lst

    else:

        max_left=max_in_range(lst[low:len(lst)/2+1],low+1,high)

        max_right=max_in_range(lst[len(lst)/2:len(lst)],low+1,high)

        return max_right if max_right>max_left else max_left



lst=[112,32,45,71238,9999,45,12,6,3]   # always Returns the mid element.

print max_in_range(lst,0,10)



def max(lst):

    global cycles

    cycles+=1

    if len(lst)==1:

        print "Cycles: ",cycles

        return lst[0]

    else:

        m=max(lst[1:])

        return m if m> lst[0] else lst[0]



print max(lst)

与问题所要求的功能相比，max函数非常简单，即函数是递归的，在运行时接受两个限制并拆分列表。函数始终返回数组中的中间元素，即9999

我需要一些关于如何满足问题要求的建议。在Java或Python或任何其他类似C的语言中。

Answer 1

您需要将电话更改为：

print max_in_range(lst,0,len(lst))

这样就不会像示例那样溢出数组。

但其余部分应该是这样的：

split = low + ((high - low) / 2)

max_left  = max_in_range(lst, low, split - 1)
max_right = max_in_range(lst, split, high)

Answer 2

请参见代码中的注释。

def max_in_range(lst, low, high):
    # If the length of the range is 1, the sole element in the range must be the maximum.
    if low == high:
        return lst[low]

    # break the array into two pieces, lst[low:low+1] / lst[low+1:high+1],
    # find the maximum in each of the pieces
    piece1_max = lst[low]
    piece2_max = max_in_range(lst, low + 1, high)

    # find the maximum of the maxima
    if piece1_max > piece2_max:
        return piece1_max
    else:
        return piece2_max

lst = [112,32,45,71238,9999,45,12,6,3]
print max_in_range(lst, 0, len(lst) - 1)