Two Solutions to the Maximum Sum Problem of Continuous Subarrays by PHP

In this paper, two solutions to the problem of finding the maximum sum of continuous subarrays by PHP are given. Share it for your reference, as follows:

Problem description

Find the maximum sum of subarrays

Title description:

Enter a shaping array with both positive and negative numbers.
One or more consecutive integers in an array make up one subarray, and each subarray has one sum.
Find the maximum value of the sum of all subarrays. The required time complexity is O (n).

There are two ways to solve the problem of maximum sum of continuous subarrays. 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;
}

More readers interested in PHP can check the topic of this site: "PHP Array (Array) Operation Skills Encyclopedia", "PHP Common Traversal Algorithms and Skills Summary", "php String (string) Usage Summary", "php Common Functions and Skills Summary", "PHP Error and Exception Handling Methods Summary", "PHP Basic Syntax Introduction Course", "php Object-Oriented Programming Introduction Course", "php+mysql Database Operation Introduction Course" and "php Common Database Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.