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

Предположим, что этот алгоритм возвращает максимальную сумму подмассива. И пусть 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, то инвариант должен подразумевать правильное решение.


algorithm invariants loop-invariant
person regsts    schedule 29.10.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если я понимаю ваш вопрос, то вот что я скажу:

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

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

Завершение: максимум - это вся сумма вашего массива a[0] + ... + a[n-1].

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

person Jake Waggoner    schedule 30.10.2018
comment
Разве это не предполагает, что все значения a_i ›= 0 ? - person Berthur; 30.10.2018
comment
@Berthur Из только что опубликованного кода это просто линейный поиск в массиве, который добавляет ключи. Если бы массив был отсортирован в порядке возрастания, то он добавлял бы только положительные числа. Но, поскольку он не говорит, что он отсортирован, и каждый шаг идет на 1, он добавит все ключи. По сути, только из приведенного выше кода вы не сможете найти максимальную сумму массива без его предварительной сортировки. - person Jake Waggoner; 30.10.2018