Rumah  >  Artikel  >  pembangunan bahagian belakang  >  php实现最大子数组的思路讲解

php实现最大子数组的思路讲解

不言
不言asal
2018-09-12 17:10:091504semak imbas

本篇文章给大家带来的内容是关于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实现求解最长公共子串思路方法

Atas ialah kandungan terperinci php实现最大子数组的思路讲解. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn