Somme de sous-réseau circulaire maximale

Question

Ceci est une question de l'algorithme de livre de Jeff erickson.

Supposons que A est un tableau circulaire. Dans ce contexte, une "sous-carrose contiguë" peut être un intervalle A [i .. j] ou un suffixe suivi d'un préfixe A [I .. n] · A [1 .. J]. Décrivez et analysez un algorithme qui trouve une sous-carrose contiguë d'A avec la plus grande somme. Le tableau d'entrée comprend des nombres réels.

Mon approche:

Il y a deux possibilités

1.) Aucun enveloppement autour (nous pouvons utiliser l'algorithme de Kadane)

2.) Emballage autour (c.-à-d .; Index de démarrage de la sous-réseau est supérieur à l'indice de fin) (j'ai un doute dans ce cas)

renvoie maintenant le maximum de deux cas en conséquence.

Pour le deuxième cas, la recherche sur Internet a fourni une approche sans preuve.

L'approche consiste à trouver la banquise avec somme minimale et à soustrayer la somme de l'ensemble de la matrice (c.-à-d. Somme (A) - Min_subarray_sum (A)). Comment cette solution est-elle correcte?

Lien pour la méthode utilisée dans le deuxième cas: https:// www. geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 1

let $ a $ Soyez votre tableau, laisse $ B $ une sous-carrose circulaire de $ A $ qui optimise $ \ sum_ {b \ in b} b $ et laisser $ C $ Soyez le sous-caral contenant tous les éléments de $ A $ qui ne sont pas dans $ B $ . Notez que $ C $ C $ est également un banquier circulaire.

vous avez $ \ sum_ {A \ in a} a=sum_ {b \ in b} b + \ sum_ {c \ in c} C $ , qui implique que $ \ sum_ {c \ in c} c=sum_ {a \ in a} a - sum_ {b \ in b} b $ . Depuis $ \ sum_ {A \ in a} a $ est une constante (WRT $ B $ ) et $ b $ optimise $ \ sum_ {b \ in b} b $ , $ C $ minimise $ \ sum_ {c \ in c} C $ .

.

En outre, au moins un de $ b $ et $ C $ est non seulement circulaire mais aussi contigu et peut donc être trouvé dans $ o (n) $ temps.