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 for the day

If a country is to be corruption free and become a nation of beautiful minds, I strongly feel there are three key societal members who can make a difference. They are the father, the mother and the teacher.

Dr. A.P.J. Abdul Kalam
Polls
Which device you use most for facebook application?
Laptop/PC
18%

 


Android
56%

 


IOS
12%

 


Blackberry
14%

 


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