An explanation of the idea of ​​​​implementing the largest subarray in PHP

This article brings you an explanation of the idea of ​​​​implementing the largest subarray in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

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

Change of the problem: The subarray with the largest continuous sum of elements in array A is meaningful only when the elements have negative numbers
Solution ideas of the divide and conquer strategy:
1. Find the elements in the array The central position mid,A[low..mid],A[mid 1..high]
2.A[low,high] is completely located in the subarray A[low..mid] low<=i<=j< =mid
3. Completely located at A[mid 1..high] mid4. Crossing the midpoint low<=i<=mid5 .Find the maximum sum of the left half (search from the middle to the left), find the maximum sum of the right half (search from the middle to the right)

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)

Related recommendations:

PHP implements two solutions to the problem of finding the maximum sum of consecutive subarrays

PHP implements the idea of ​​​​finding the longest common substring

The above is the detailed content of An explanation of the idea of ​​​​implementing the largest subarray in PHP. For more information, please follow other related articles on the PHP Chinese website!