多个不重叠连续最优子序列和问题

Question

已知一个序列[8 6 5 6 1 1 4 4 5 2 6 8]，和三个整数分别是3，2和4，求窗口长度分别等于这三个整数的的三个连续子序列，并且他们之间两两不相交，使得他们的和为最大。从肉眼看，最优序列分别是长度为4：【8 6 5 6】索引[0:4]，长度为3【4 4 5】索引[6:9]，长度为2【6 8】索引[10:12],这三个连续子序列的和为52。我用DP尝试了很久，一直没有获得理想的结果。

Answer 1

The logic flow is straight in recursive sql with BFS which may have some limited optimization, eg, both 2+3 and 3+2 cut off at the same position may have different sum values and take the larger one and continue searching the largest 4 value in following steps.

What I am wondering is how your guys thinking about DP approach, looping from the first input number to the last input number for given sequence. The pattern of obtaining max sum value, 2,3,4 or 4,2,3, or ..., can obviously change each time adding in a number in given sequence. So it is like dancing grouping in order to get the max sum value. With M input, it groups like 3,4,2, with M+1 it groups like 4,3,2, with M+2 it groups like 2,4,3, etc. So any previous result does not really help on following result generally.