This is my attempt at solving SUMTRIAN.Please tell me where i am wrong.
Firstly your approach to find max element in final row is wrong. Secondly, you are using greedy approach here i guess, which is wrong.
It is not necessary that you get maximum score by choosing maximum value every turn!!
Take this triangle-
1 1 5 1 1 5 100 1 5 1 1 1 5
If you go by choosing only maximum value, your final score will be 21, while you can get a better score. Remember, you can choose values which are only directly below or diagonally right to current one.
Can you give me a hint to solve this? This has been the hardest question i’ve encountered till now.
You need to learn dynamic programming for this. Thats your hint
Thank you.I’ll learn it right away.