Une explication de l'idée d'implémenter le plus grand sous-tableau en PHP

Ce que cet article vous apporte, c'est une explication de l'idée d'implémenter le plus grand sous-tableau en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

key
buy
sell
for i=0;i<n;i++
    for j=i+1;j<n;j++
        p=key=arr[j]-arr[i]
        if !key key=p
        if key<p buy=i sell=j

Variation du problème : le sous-tableau avec la plus grande somme continue d'éléments dans le tableau A n'a de sens que lorsque les éléments ont des nombres négatifs
L'idée de solution de la stratégie diviser pour régner :
1. Trouvez le tableau La position centrale mid,A[low..mid],A[mid+1..high]
2.A[low,high] est complètement située dans le sous-tableau A[low ..mid] low<=i< =j<=mid
3 Complètement situé à A[mid+1..high] mid4. =i<=mid5. Trouvez la somme maximale de la moitié gauche (recherchez du milieu vers la gauche), trouvez la somme maximale de la moitié droite (recherchez du milieu vers la droite)

leftSum left
for i=mid;i>=low;i--
    sum=sum+A[i]
    if sum>leftSum
        leftSum=sum
        left=i
rightSum right
for j=mid+1;j<=high;j++
    sum+=A[j]
    if sum > rightSum
        rightSum=sum
        right=i
6.递归调用
    mid=(low+high)/2
    find(A,low,mid)
    find(A,mid+1,high)
    findCross(A,low,mid,high)

Recommandations associées :

Explication de 2 solutions au problème de trouver la somme maximale de sous-tableaux consécutifs en PHP

Comment résoudre la sous-chaîne commune la plus longue en PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!