Использование глобальных переменных в функции 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

Посмотрите на структуру коды: нет рекурсивного вызова лилии; когда он инициализирует максимум = 1 в строке 42, это только время выполнения этого оператора. Все остальное сделано в пределах _lis, где максимум обновляется, никогда не восстанавливается до 1.

Я рекомендую вам найти другой код для изучения. Этот пример показывает вредные привычки при обработке переменных максимум и arr - автор игнорирует силу рекурсии здесь, используя логику в стиле цикла. Вы можете сделать классное упражнение из-за его обновления в программу, которую легко читать и поддерживать.

В динамическом программировании единственными глобальными переменными должны быть для memoization. Фактически, в этом примере используется no memoization - это означает, что это не динамическое программирование. Короче говоря, должен быть список заметок, в котором memo [n] содержит значение из _lis (arr, n). Рекурсивные вызовы должны идти не дальше одного уровня, так как _lis вернет это сохраненное значение. Ответ в конце - это просто max (memo).

См. Страницы WIkipedia на dynamic programming и memoization.