# 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

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
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

Success is not built on success. It's built on failure. It's built on frustration. Sometimes its built on catastrophe.

Sumner Redstone

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

Send your details, our executive will contact you

Email:

Mobile:

Location:

Polls
Which device you use most for facebook application?
Laptop/PC
15%

Android
49%

IOS
32%

Blackberry
4%

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