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實作最大子數組的思路講解的詳細內容。更多資訊請關注PHP中文網其他相關文章！