Máxima suma de subaray circular

Question

Esta es una pregunta de los algoritmos del libro de Jeff Erickson.

Supongamos que A es una matriz circular. En este ajuste, una "subarrición contigua" puede ser un intervalo a [i .. j] o un sufijo seguido de un prefijo A [i .. n] · A [1 .. j]. Describa y analice un algoritmo que encuentra un subarray contiguo de A con la suma más grande. La matriz de entrada consiste en números reales.

Mi enfoque:

Hay dos posibilidades

1.) Sin envolver alrededor (podemos usar el algoritmo de Kadane)

2). Envolver alrededor (es decir, el índice de inicio del sumarray es mayor que el índice final) (tengo dudas en este caso)

Ahora devuelva el máximo de dos casos como resultado.

Para el segundo caso, la búsqueda en Internet proporcionó un enfoque sin pruebas.

El enfoque es encontrar la sumarray con suma mínima y restarla de la suma de la matriz completa (es decir, suma (A) - MIN_SUBARRAY_SUM (A)). ¿Cómo es correcta esta solución?

Enlace para el método utilizado en el segundo caso: https:// www. geeksforgeeeks.org/maximum-contiguous-circular-sum/

Answer 1

Deja que $ A $ sea su matriz, deja $ b $ un subarray circular de $ A $ que maximiza $ \ sum_ {b \ in b} B $ , y deja $ C $ Be the Subarry que contiene todos los elementos de $ a $ que no están en $ B $ . Observe que $ C $ es también un subarray circular.

Tienes $ \ sum_ {a \ in a} a=sum_ {b \ in b} B + \ sum_ {c \ in c} C $ , lo que implica que $ \ sum_ {c \ in c} c=sum_ {a \ in a} a - \ sum_ {b \ in b} B $ . Desde $ \ sum_ {a \ in a} a $ es un constante (WRT $ b $ ) y $ b $ maximiza $ \ sum_ {b \ in b} B $ , $ C $ minimiza $ \ sum_ {c \ in c} C $ .

Además, al menos uno de $ b $ y $ c $ no solo es circular, sino también Por lo tanto, contiguo y se puede encontrar en $ o (n) $ tiempo.