Maximum sum in sequence

MEDIUM

Given a string of integers separated by a single space.

Find a sequence of numbers in which the sum of the elements is maximum.

For example, for string "-2 1 -3 4 -1 2 1 -5 4" solution is the sequence "4 -1 2 1" with sum = 6.

Print max sum only.

This sequence can be only one number (see example with negative numbers).

Example #1

Input

-8 -3 -6 -2 -5 -4

Output

-2

Example #2

Input

-2 1 -3 4 -1 2 1 -5 4

Output

Solution

<?php
$line = trim(fgets(STDIN));
$nums = explode(' ', $line);

$numsCount = count($nums);

$maxSumCurrent = $nums[0];
$maxSumTotal = $nums[0];

for ($i = 1; $i < $numsCount; $i++) {
    $num = $nums[$i];

    $maxSumCurrent += $num;
    
    if ($maxSumCurrent < $num) {
        $maxSumCurrent = $num;
    }

    if ($maxSumCurrent > $maxSumTotal) {
        $maxSumTotal = $maxSumCurrent;
    }
}

echo $maxSumTotal;

Tests

Test #1	Loading...
Test #2	Loading...
Test #3	Loading...
Test #4	Loading...

Maximum sum in sequence

Example #1

Input

Output

Example #2

Input

Output

Solution

Tests

Result