Somma massima del subarray circolare

Question

Questa è una domanda dagli algoritmi del libro di Jeff Erickson.

Supponiamo che A è un array circolare. In questa impostazione, un "sottotatore contiguo" può essere un intervallo A [I .. J] o un suffisso seguito da un prefisso A [i .. n] · A [1 .. J]. Descrivi e analizza un algoritmo che trova un sottotatore contiguo di A con la somma più grande. L'array di ingresso è costituito da numeri reali.

Il mio approccio:

Ci sono due possibilità

1.) Nessuna confezione in giro (possiamo usare l'algoritmo di Kadane)

2.) Avvolgisci (cioè, l'indice iniziale del sottoarray è maggiore dell'indice finale) (ho dubbi in questo caso)

Ora restituisce il massimo di due casi come risultato.

Per il secondo caso, la ricerca su Internet ha fornito un approccio senza prova.

L'approccio è trovare il sottoronzo con la somma minima e sottrarre dalla somma dell'intero array (cioè; somma (A) - min_subarray_sum (A)). Come è corretta questa soluzione?

Link per il metodo utilizzato nella seconda custodia: https:// www. geeksforgeeks.org/maximum-contiging-circular-sum/

Answer 1

Let $ A $ Be your array, let $ B $ una sottouria circolare di $ A $ che massimizza $ \ sum_ {b \ in b} B $ , e lascia che $ c $ Sii il sottotitolo che contiene tutti gli elementi di $ a $ che non sono in $ B $ . Si noti che $ c $ è anche un sottotay circolare.

Hai $ \ sum_ {a \ in a} A=sum_ {b \ in b} b + \ sum_ {c \ in c} c $ , il che implica che $ \ sum_ {c \ in c} c=sum_ {a \ in a} A - \ sum_ {b \ in b} B $ . Poiché $ \ sum_ {a \ in a} A $ è una costante (Wrt $ B $ ) e $ B $ Massimizza $ \ sum_ {b \ in b} B $ , $ c $ Riduci da minimizza $ \ sum_ {c \ in c} c $ .

Inoltre, almeno una delle classifiche $ B $ e $ c $ non è solo circolare ma anche Contiguo e può quindi essere trovato in $ o (n) $ tempo.