Инвариант алгоритма

Question

Предположим, этот алгоритм возвращает максимальную сумму подмассива. И пусть a [] будет массивом длины n.

randmax = 0
maximum = 0
for 0 <= i < n 
    randmax = randmax + a_i
    if randmax > max 
    max = randmax
    if randmax < 0 
    randmax = 0

Как найти инвариант цикла, который сохраняется до выполнения и, конечно, до и после итерации цикла, а когда n-1, то инвариант должен подразумевать правильное решение.

Answer 1

Если я понимаю, что вы вопрос, то это то, что ID говорит:

Инициализация: для начала сумма равна 0, поэтому ваш максимум равен 0

Техническое обслуживание: максимальная сумма пока равна сумме [0] + ... + a [i-1]

Окончание: max - это полная сумма вашего массива a [0] + ... + a [n-1].

Таким образом, инвариант цикла состоит в том, что ваша сумма / максимум в любой момент времени равна [0] + ... + a [i-1] и состоит только из чисел, найденных в вашем массиве для начала.