In the intial Coding round I was asked 2 questions

1. Given an array of package of length n, you can merge ith package with i+1 th package if weight[i] < weight[i+1]. After this operation, the number of packages reduces by 1 and the weight of the package i+1 increases by weight[i]. You can merge any number of package.

Find the maximum weight of the package possible after merging.
Eg:
Input
4
[ 20, 13, 8, 9]

Output
50

Explanation:

Combine package at 3 and 4 index it becomes [20, 13, 17].
Combine package at 2 and 3 index it becomes [20, 30].
Combine package at 1 and 2 index it becomes [50].

Input
4
[ 30, 15, 5, 9]

Output

30

Explanation

Merge the last two [30, 15, 14]. No other merge possible.

I know we have to use backtracking/ dynamic programming to solve it but i am clueless on how to code it. It will be helpful if someone posts a working solution for it.