PHP Coding Puzzle 3 : Find Contiguous Subarray with the Largest Sum

Possible solution

Here’s one way to solve the problem:

function maxSubArray($nums) {
  $n = count($nums);
  $maxSum = $nums[0];
  $currSum = $nums[0];

  for ($i = 1; $i < $n; $i++) {
    // Calculate the current sum as the maximum of the current element
    // and the current sum plus the current element
    $currSum = max($nums[$i], $currSum + $nums[$i]);

    // Update the maximum sum if the current sum is greater
    $maxSum = max($maxSum, $currSum);
  }

  return $maxSum;
}

The function uses a dynamic programming approach to find the maximum sum of any contiguous subarray in the array. It initializes two variables, $maxSum and $currSum, to the first element of the array. It then loops through the array starting at the second element.

For each element, it calculates the current sum as the maximum of the current element and the current sum plus the current element. It then updates the maximum sum if the current sum is greater. This way, the function keeps track of the largest sum seen so far and the largest sum that includes the current element.

At the end of the loop, the function returns the maximum sum seen. This is the maximum sum of any contiguous subarray in the array.