I'm going to exlain my approach for the "find max sub array" part of this problem.:

Let's say you have a sub-array, initially it's empty. For any item in the original array, you basically have 2 choices: 1. Add this item to the current sub-array. 2. Make a new sub-array starting from this item.

With dynamic programming, you can keep tracking the max-sum of the sub-array for both of the choices you've made at each item in the original array.

PHP code for this approach:

function maxSubarray($arr)
{
    $dp = [];
    $maxArr = PHP_INT_MIN;
    foreach ($arr as $i => $v) {
        //Track the sum if we make a new sub-array with $v
				$dp[$i][0] = $v;
				
				// Track the sum if we append the sub-array with $v
        $dp[$i][1] = max($dp[$i - 1] ?? [0]) + $v;
				
        $maxArr = max($maxArr, ...$dp[$i]);
    }

    return $maxArr;
}