Two solutions to the problem of finding the maximum sum of consecutive subarrays in PHP

This article mainly introduces two solutions to the problem of finding the maximum sum of continuous subarrays in PHP, involving PHP's array traversal, judgment, operation and other related operating skills. Friends in need can refer to it

The examples in this article describe two solutions to the problem of finding the maximum sum of consecutive subarrays in PHP. Share it with everyone for your reference, the details are as follows:

Problem description

Find the maximum sum of subarrays

Title description:

Input an integer array, there are positive and negative numbers in the array.
One or more consecutive integers in the array form a subarray, and each subarray has a sum.
Find the maximum value of the sum of all subarrays. The required time complexity is O(n).

Regarding the problem of the maximum sum of consecutive subarrays, there are two solutions, one is dynamic programming

The solution is as follows:

function getMaxSubSum($arr){
  $curSum = $arr[0];
  $maxSum = $arr[0];
  for($i = 1; $i < count($arr); $i++){
    if($curSum > 0) $curSum += $arr[$i];
    else $curSum = $arr[$i];
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  return $maxSum;
}

There is also a scanning method

function getMaxSubSum($arr){
  $curSum = 0;
  $maxSum = 0;
  for($i = 0; $i < count($arr); $i++ ){
    $curSum += $arr[$i];
    if($curSum <= 0) $curSum = 0;
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  if($maxSum == 0){
    $maxSum = $arr[0];
    for($i = 1; $i < count($arr); $i++){
      if($maxSum < $arr[$i] ) $maxSum = $arr[$i];
    }
  }
  return $maxSum;
}

You may be interested Article:

php Get ajax headers method and content example explanation

The most basic operation tutorial of using Queue in Laravel

Detailed explanation of Yaf framework PHPUnit integration test method

##

The above is the detailed content of Two solutions to the problem of finding the maximum sum of consecutive subarrays in PHP. For more information, please follow other related articles on the PHP Chinese website!