给一个长度为n的数组，一个区间每次可以合并左边或者右边的一个数，如果区间和小于它。求从每个位置出发，最大可以合并的区间和。
样例1：
3
2 1 4
结果 2 7 4，解释从1出发先合并2，得到（2，1）再合并4
样例2：
5
2 3 6 1 4
结果 11 9 6 11 4

区间dp

写了下代码，样例没啥问题。
思路是，dp(l, r)表示，已经选择了区间[l, r]时，可以合并的区间和的最大值。默认值是区间lr的和，可以用前缀和O1求。如果区间左边的数比这个默认值大，dp值就等于max(dpl-1, r和dpl, r)。右边同理。边界条件是l＝1，r＝n。时间复杂度On²，空间复杂度你愿意的话可以On

对于每个下标i，直接dfs暴力即可。复杂度nlog^2a，a是指数组的最大值。首先，由于我们区间合并时，加的数是大于这个区间合的，所以每次合并后，区间合最少*2，所以区间长度不超过loga。直接暴力的话，看似每个下标的dfs的复杂度是2^loga也就是a，实则不然，我们可以发现，在选择合并左边还是右边时，如果我们选择了值更大的一边，则另一边就永远取不到了，所以，对于每次选择左边还是右边时，我们选择更大的一边一直加到无法加，然后max一下，之后再去选择较小的一边，把小的那一边合并，此时数组长度加一。如此循环往复，直到小的那边加不进去为止，最多加loga次，每次把大的一边加到底也是loga，复杂度log^2a。