Quel est exactement un vide Sous-tableau

Question

J'ai lu la question dans l'Exercice 4.1-4 en Introduction Aux Algorithmes:

Supposons que nous modifier la définition du maximum de subarray problème pour permettre à la résultat à un vide subarray, où la somme des valeurs d'un vide subarray est de 0.Comment voulez-vous modifier les algorithmes qui ne permettent pas de vide sous-réseaux afin de permettre un vide subarray être le résultat?

Je ne peux pas obtenir ce qui est un vide sous-tableau.

Je suis tombé sur le moment que d'un seul numéro peut être retourné si le tableau est constitué d'éléments négatifs seulement.

Svp quelqu'un peut-il expliquer le concept de vide sous-réseau?Et comment pouvons-nous avoir un vide de sous-réseau?

Même si un seul élément est retourné, cela signifie encore que sous-ensemble n'est pas vide.Veuillez effacer le doute.

Edit:

Pour rendre cela plus clair comme question si je prends un tableau d'éléments:

[-3,-4,-1,-8]

La réponse serait -1 ou 0?Veuillez expliquer si pourquoi il devrait être 0 et comment pouvons-nous conclure un vide sous-tableau.

Je vous remercie.

Answer 1

Si vous avez ce tableau: $[-2,-10,-5]$, et le problème précise que vous devez retourner à la somme de la valeur maximale de subarray dont la longueur est au moins $1$, vous retournerez la somme de la subarray $[-2]$, qui est $-2$.So far So good?

Maintenant, l'accent ici parce que c'est où vous êtes le plus probablement de la difficulté à:

Le problème est maintenant modifié.Le problème maintenant, vous permet de revenir à un vide subarray, ce qui signifie, vous pouvez revenir à un subarray qui est vide - un subarray qui n'a pas d'éléments.Ours avec moi:

En mathématiques, un "vide somme" est une somme, où le nombre de termes est égale à zéro. De vérifier.

De même, en informatique, un "vide subarray" est un subarray dans lequel le nombre de termes est égale à zéro. C'est juste la définition. C'est juste un subarray dont la somme est évaluée à zéro.

Maintenant, concernant la version remaniée du problème, ce qui serait mieux, d'y revenir $[-2]$ dont la somme donne $-2$, ou de retourner le vide subarray $( [ \ \ \ ] )$ dont la somme donne $0$?

Answer 2

Un subarray de longueur zéro est vide.

Étant donné un tableau $A[1],\ldots,A[n]$, un subarray est spécifié par une paire d'indices $i \leq j$.Ceux-ci correspondent à la subarray $A[i],\ldots,A[j]$ de longueur $j-i+1$.Si nous permettons également à $j = i-1$ puis, nous avons un vide subarray de longueur $j-i+1 = 0$, dont la somme est égale à zéro.

---

Dans le délai maximum de subarray problème, on nous donne un tableau $A[1],\ldots,A[n]$, et voulez trouver un subarray dont la somme est maximale.Si nous ne permettent pas de vide sous-tableaux, cela signifie que nous sommes à la recherche de la valeur maximale de $$ A[i] + \cdots + A[j], $$ où $1 \leq i \leq j \leq n$.Si nous sommes permettant à vide des sous-tableaux, puis nous prenons le maximum de ce que $0$, qui est la somme de la vide subarray.

Cela ne fait qu'une différence si toutes les entrées du tableau sont négatifs.La somme maximale d'un non-vide subarray est dans ce cas la durée maximale de l'élément $A[i]$, qui est la somme de la subarray $A[i]$ de longueur $1$.Le vide subarray, cependant, a une plus grande somme: $0$.Par conséquent, si le vide subarray n'est pas autorisé, la réponse devrait être $\max_i A[i]$, et si elle est autorisée, la réponse devrait être $0$.