この記事では、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<= を通過していますmid
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 中国語 Web サイトの他の関連記事を参照してください。