sum maximum value in triangle

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



Solution:
<?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;
?>

Name
Email
Comments
Back
Funding

We need your support to operate it properly. We have lots of ideas but less fund, so help us with your funding.

Thoughts of the day

A person who never made a mistake never tried anything new

Albert Einstein
Sell your product online

Do you want to sell products online with no extra cost?

Send your details, our executive will contact you

Email:

Mobile:

Location:

Polls
What you like most in facebook?
News
100%

 


Games

Images

Videos

Tutorial On Request
Q. Ask us for any tutorial or any thing which helps to build your career better.
Email:
Query: