Find sum of maximum values in each row of a triangle

Imagine you have a row of numbers like below(a triangle). By starting at the top of the triangle, find the maximum number in each line and sum them up. Example below.

5

9 6

4 6 8

0 7 1 5

Answer:

5+9+8+7=29

Write a code to find the maximum total from top to bottom. Assume triangle can have at most 100000 rows.

Input/Output Specifications Input Specification:

A string of n numbers (where 0<=n<=1010)

eg. 5#9#6#4#6#8#0#7#1#5

Output Specification:

A sum of the max numbers in each line(as string) Or Output Invalid in case of Invalid input/triangle.

Examples:

eg1:

Input: 5#9#6#4#6#8#0#7#1#5

Output: 29

eg2:

Input: 5#9#6#4#6#8#0#7#1

Output: Invalid

eg3:

Input: 5#9##4#6#8#0#7#1

Output: Invalid

<?php
function getresult($values)
{
	$arrValues=explode("#",$values);
	$cntValues=count($arrValues);

	if($cntValues==1) { //Input:5
		$res=isset($arrValues[0])?$arrValues[0]:'Invalid';
	}
	else if($cntValues==2) { //Input #2 or 3#
		if((isset($arrValues[0]) && $arrValues[0] >0) && (isset($arrValues[1]) && $arrValues[1] >0)) {
			$res='Invalid';
		}
		else {
			$res=isset($arrValues[0])?$arrValues[0]:$arrValues[1];
		}
	}
	else {
		$k=0; //Current row index
		$j=1; //First row (previous row)
		$i=2; //element length in row (2:second row,3:third row,4:forth row)
		$next=1; //Element count till row
		$data=0; //Total sum data

		//If next is smaller than total count
		while($next<=$cntValues)
		{
			//For being a triangle, there should be atleast 3 elements
			$next=$i+$j;
			if($cntValues < $next) {
				$res='Invalid';
			}
			else {
				//For first row
				if($j==1) {
					$newarr[] = array_slice($arrValues,0,1);
					$data =$data + $newarr[$k][0]; //First row data
				}
				$k++;
 
				//Calculation for 2nd and more rows
				$newarr[] = array_slice($arrValues,$j,$i);
				rsort($newarr[$k]); //Sort on each row
				$data =$data + $newarr[$k][0];

				//Last row
				if($next==$cntValues) {
					$res=$data;
					break;
				}
			}
			$i++;
			$j=$next;
		}
	}
	return $res;
}

$values="5#9#6#4#6#8#0#7#1#5";	//Input string

$res=getresult($values);
echo "Output: ".$res;
?>