Soma máxima de subarray circular

Question

Esta é uma questão dos algoritmos do livro por Jeff Erickson.

Suponha que um seja uma matriz circular. Nesta configuração, um "subarray contíguo" pode ser um intervalo A [i .. j] ou um sufixo seguido por um prefixo [I .. n] · A [1 .. j]. Descreva e analise um algoritmo que encontre uma subarray contígua de um com a maior soma. A matriz de entrada consiste em números reais.

minha abordagem:

Existem duas possibilidades

1.) Nenhum envolvimento (podemos usar o algoritmo de Kadane)

2.) Envolvendo (isto é, o índice inicial da subarray é maior que o índice final) (tenho dúvidas neste caso)

Agora retorne o máximo de dois casos como resultado.

Para o segundo caso, pesquisar na Internet forneceu uma abordagem sem provas.

A abordagem é encontrar a subarray com soma mínima e subtrai-a da soma de toda a matriz (ou seja, soma (a) - min_subarray_sum (A)). Como esta solução está correta?

Link para o método usado no segundo caso: https:// www. geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 1

Deixe $ a $ a $ Seja sua matriz, deixe $ b $ uma subarray circular de $ a $ que maximiza $ \ sum_ {b \ in b} B $ , e deixe $ c $ Seja o subarray que contém todos os elementos da $ a $ que não estão em $ B $ . Observe que $ c $ também é uma subarray circular.

Você tem $ \ sum_ {\ in a} a=sum_ {b \ in b} b + \ sum_ {c \ in c} c $ , o que implica que $ \ sum_ {c \ in c} c=sum_ {a \ in a} a - \ sum_ {b \ in b} b $ . Como $ \ sum_ {a \ em A} A $ é uma constante (wrt $ B $ ) e $ b $ maximiza $ \ sum_ {b \ in b} b $ , $ c $ minimiza $ \ sum_ {c \ in c} c $ .

Além disso, pelo menos uma das $ B $ e $ C $ não é apenas circular, mas também contíguo e, portanto, pode ser encontrado em $ o (n) $ tempo.