The input will be a right triangle of numbers. Let’s say the input is :
1 2 3
Number of lines is 3 here. You need to find a path from line 1 till the last line such that the sum of numbers on the path is maximum.
One constraint though. For a number on a line, you need to pick the next number from the below line that’s either in the same column or the column to its immediate right. E.g for 1 in line 2, you can pick 1 or 2 from the line below, but not 3.
In the above example, the result path is 1-2-3 with sum=6.
Please inform if any confusion rises.
I understand your example but
But code-chef example is
1 2 3
So the path would be (1(line-1)+2(line-2)+3(line-3))=6 but codechef says 5 how ??
Sorry for the late reply. After 2 on second line, the next number must lie either in the same column as previous one or the column to its immediate right. 3 is not .