PHPで最大の部分配列を実装する考え方の説明

この記事では、PHP で最大の部分配列を実装するアイデアについて説明します。一定の参考値があります。必要な友人は参照してください。お役に立てれば幸いです。

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

問題の変更:配列 A 内の要素の連続和が最大の部分配列は、要素が負の数を持つ場合にのみ意味を持ちます
分割統治戦略の解決策のアイデア:
1.配列内の要素を検索します。中央の位置 Mid,A[low..mid],A[mid 1..high]
2.A[low,high] は完全に部分配列 A[low..mid] に位置します。 ] low<=i<=j< =mid
3.完全に A[mid 1..high]に位置していますmid4.中点 low<=i<= を通過していますmid5 .左半分の最大和を求めます（中央から左に向かって検索）、右半分の最大和を求めます（中央から右に向かって検索）

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)

関連する推奨事項:

PHP は、連続する部分配列の最大合計を求める問題に対する 2 つの解決策を実装します

PHP は、最長の共通部分文字列

を見つけるという考え方

以上がPHPで最大の部分配列を実装する考え方の説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。