
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; ?>
We need your support to operate it properly. We have lots of ideas but less fund, so help us with your funding.
A perfection of means, and confusion of aims, seems to be our main problem
Do you want to sell products online with no extra cost?
Send your details, our executive will contact you