MaximumSubarray53.php

<?php

declare(strict_types=1);

namespace Fathom\Leetcode\Easy;

/*
https://leetcode.com/problems/maximum-subarray/
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

 */

class MaximumSubarray53
{
    // O(n)
    public static function maxSubArray(array $nums): int
    {
        $res = PHP_INT_MIN;
        $curSum = 0;

        foreach ($nums as $num) {
            $curSum = max($curSum + $num, $num);
            $res = max($res, $curSum);
        }

        return $res;
    }

    // O(n*log(n))
    public static function maxSubArray2(array $nums): int
    {
        if (empty($nums)) {
            return 0;
        }

        return self::helper($nums, 0, count($nums) - 1);
    }

    private static function helper(array $nums, int $left, int $right): int
    {
        if ($left >= $right) {
            return $nums[$left];
        }

        $mid = (int) ($left + ($right - $left) / 2);

        $lmax = self::helper($nums, $left, $mid - 1);
        $rmax = self::helper($nums, $mid + 1, $right);

        $mmax = $nums[$mid];
        $t = $mmax;
        for ($i = $mid - 1; $i >= $left; --$i) {
            $t += $nums[$i];
            $mmax = max($mmax, $t);
        }

        $t = $mmax;
        for ($i = $mid + 1; $i <= $right; ++$i) {
            $t += $nums[$i];
            $mmax = max($mmax, $t);
        }

        return max($mmax, $lmax, $rmax);
    }
}