Trouver deux sous-tableaux contigus avec la plus grande différence

Question

Voici une question d'entretien que j'ai vue sur quelques sites.Les gens prétendent qu'un O(n) une solution est possible, mais je me suis creusé la tête ces 2 derniers jours et je n'arrive pas à trouver de solution, ni à en trouver nulle part sur le web.

Étant donné un tableau d'entiers, trouvez deux sous-tableaux disjoints et contigus tels que la différence absolue entre la somme des éléments de chaque sous-tableau soit aussi grande que possible.

Exemple d'entrée : (2, -1, -2, 1, -4, 2, 8)

Exemple de sortie : ((1, 4), (5, 6))

Le résultat ci-dessus correspond aux indices de ces deux sous-tableaux : ((-1, -2, 1, -4,), (2, 8))

J'ai essayé de réduire ce problème au Problème de sous-tableau maximum mais sans succès.

Answer 1

Les deux sous-tableaux étant disjoints, il existe au moins un index millions de dollars de telle sorte qu'un sous-tableau entier se trouve $\leq m$ et l'autre sous-tableau se trouve $\gt m$.

Mais nous ne savons pas ce que c'est millions de dollars est, au préalable.Alors passons en revue tous les $n$ possibilités de millions de dollars.Maintenant, si un millions de dollars est résolu, le problème se réduit alors au problème du sous-tableau maximum et au problème du sous-tableau minimum.En effet, pour que la différence absolue soit la plus grande, un côté de millions de dollars devrait avoir le sous-réseau maximum possible, et l'autre côté devrait avoir le sous-réseau minimum possible.Nous essayons donc ces deux options et prenons la différence absolue maximale entre les deux.

Mais c'est toujours $\mathcal{O}(n^2)$, parce qu'il y a $n$ différentes valeurs de millions de dollars, et pour chacune de ces valeurs, nous devons dépenser $\mathcal{O}(n)$ temps pour calculer les sous-tableaux minimum et maximum nécessaires.

L'observation suivante est de noter qu'un seul $\mathcal{O}(n)$ L'exécution de l'algorithme de sous-tableau maximum sur l'ensemble du tableau peut en fait nous donner l'une des valeurs nécessaires pour toutes les valeurs de millions de dollars:

Given: int A[n]

MaxSubarrayTill[0] = A[0]
MaxSubarrayEndingAt[0] = A[0]
for(i = 1; i < n ; i++)
{
    MaxSubarrayEndingAt[i] = max{A[i], MaxSubarrayEndingAt[i - 1] + A[i]}
    MaxSubarrayTill[i] = max{MaxSubarrayTill[i - 1], MaxSubarrayEndingAt[i]}
}

Ici, $ ext{MaxSubarrayTill}[i]$ désigne le sous-tableau de somme maximale qui se termine $\le i$, et $ ext{MaxSubarrayEndingAt}[i]$ désigne le sous-tableau de somme maximale qui se termine à l'index $i$.

De même, on peut calculer le $ ext{MinSubarrayTill}[i]$ tableau dans $\mathcal{O}(n)$ temps.Et en répétant les deux mêmes algorithmes à l’envers (c.-à-d.de la fin du tableau au début), on peut obtenir $ ext{MaxSubarrayFrom}[i]$ et $ ext{MinSubarrayFrom}[i]$.

Donc dans $\mathcal{O}(n)$ Une fois que nous avons précalculé toutes les valeurs dont nous avions besoin dans le premier algorithme, auquel nous pouvons maintenant revenir.Interagir sur toutes les valeurs de millions de dollars, et trouvez la plus grande différence absolue dans $\mathcal{O}(n)$ temps.

Si le problème stipule également que les deux sous-tableaux doivent être adjacents, alors nous pouvons laisser de côté $ ext{MaxSubarrayTill}[i]$ et ses tableaux analogues, et ne considérons que $ ext{MaxSubarrayEndingAt}[i]$ et ses trois autres tableaux analogues.Le reste de l'algorithme reste le même.