在 python 函数中使用全局变量

Question

我正在针对最长递增子序列问题进行此解决方案，并注意到子序列长度最大值的全局变量正在运行主函数的驱动程序以及计算最长子序列的实际函数中重新定义：

# global variable to store the maximum
global maximum
def _lis(arr , n ):
    # to allow the access of global variable
    global maximum
    # Base Case
    if n == 1 :
        return 1
    # maxEndingHere is the length of LIS ending with arr[n-1]
    maxEndingHere = 1
    """Recursively get all LIS ending with arr[0], arr[1]..arr[n-2]
       IF arr[n-1] is maller than arr[n-1], and max ending with
        arr[n-1] needs to be updated, then update it"""
    for i in xrange(1, n):
        res = _lis(arr , i)
        if arr[i-1] < arr[n-1] and res+1 > maxEndingHere:
            maxEndingHere  = res +1
    # Compare maxEndingHere with overall maximum.And update
    # the overall maximum if needed
    maximum = max(maximum , maxEndingHere)
    return maxEndingHere
def lis(arr):
    # to allow the access of global variable
    global maximum
    # lenght of arr
    n = len(arr)
    # maximum variable holds the result
    maximum = 1
    # The function _lis() stores its result in maximum
    _lis(arr , n)
    return maximum

似乎每次进行递归调用时，最大值都会被重置。在函数的局部范围内重新定义全局变量的目的是什么？

Answer 1

您必须在函数中使用 global 关键字才能全局更改变量;如果不使用该关键字，它将创建一个具有相同名称的局部范围的变量。语句 global maximum 不会"重新定义"变量，但它告诉 Python 如果在此函数中maximum设置为某个值，则全局变量将更改。

In [1]: a = 42
In [2]: def f():
   ...:     a = 23
   ...:
In [3]: f()
In [4]: a
Out[4]: 42
In [5]: def g():
   ...:     global a
   ...:     a = 23
   ...:
In [6]: g()
In [7]: a
Out[7]: 23

Answer 2

查看代码结构：没有对 LIS 的递归调用; 当它在第 42 行初始化 Maximum = 1 时，这是唯一一次执行此语句。 其他一切都在 _lis 内完成，其中最大值仅更新，永远不会重置为 1。

我建议你找其他代码来研究。 这个例子显示了处理变量 max 和 arr 的坏习惯——作者在这里忽略了递归的力量，使用循环式逻辑。 你可以做一个很好的课堂练习，把它升级到一个易于阅读和维护的程序。

---

在动态规划中，唯一的全局变量应该是用于记忆。 事实上，这个例子没有使用记忆——这意味着它不是动态编程。 简而言之，应该有一个备忘录列表，其中备忘录[n]保存_lis（arr，n）的值。 递归调用不应超过一级深度，因为_lis将返回此存储值。 最后的答案很简单 max（备忘录）。

请参阅WIkipedia关于动态编程和记忆的页面。