Maximum Subarray Sum
PHP
Hard
4 views
Problem Description
Print the maximum subarray sum (Kadane).
Input Format
First n. Next line n integers.
Output Format
One integer maxSum.
Sample Test Case
Input:
9
-2 1 -3 4 -1 2 1 -5 4
Official Solution
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$i=0; $n=intval($tokens[$i++] ?? 0);
$best=null; $cur=0;
for($k=0;$k<$n;$k++){
$v=intval($tokens[$i++] ?? 0);
if($best===null) $best=$v;
$cur=max($v,$cur+$v);
if($cur>$best) $best=$cur;
}
echo ($best===null?0:$best);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!