我想找到一种方法，可以通过对树的跨度总和进行评分，并选择得分最高的二叉树，以通过回溯使总和最大化。

假设，我有以下句子：

string = "Revenue was 19.9 million"

spans数组代表相应(i, j)位置上的span得分。这里：j=i+1

例如，

score(0, 1)=-100.0对应跨度"Revenue"；

score(0, 4)=100.0对应跨度"Revenue was 19.9 million"；

score(1, 4)=100.0对应跨度"was 19.9 million"；

等等 ...

                                               #  1 2 3 4
spans = [[-100.0, -100.0, -100.0,  100.0],     # 0
         [ 0,     -100.0, -100.0,  100.0],     # 1
         [ 0,       0 ,   -100.0,  100.0],     # 2
         [ 0,       0,      0,    -100.0]]     # 3
         

预期树-(Revenue (was (19.9 million)))对应的跨度(0, 4)，(1, 4)，(2, 4)。

虽然，我得到-(Revenue was 19.9 million)与下面的代码。

我试着做：

class MaxSpanCalculator:

    def __init__(self, s, spans):
        self.sentence = s.split(" ")
        self.spans = spans
        self.splits = []

    def get_max_span_sentence(self):
        n = len(self.sentence)
        # Initialize the splits array
        for i in range(n):
            s = []
            for j in range(n):
                s.append(-1)
            self.splits.append(s)

        # Here Using spans array itself as dp array
        for l in range(1, n+1):
            i = 0
            j = i + l - 1
            while j<n:
                if i!=j:
                    for p in range(i,j):
                        if self.spans[i][j] < self.spans[i][p] + self.spans[p+1][j]:
                            self.splits[i][j] = p
                            self.spans[i][j] = self.spans[i][p] + self.spans[p+1][j]
                i = i + 1
                j = j + 1

        print("Max span value: " + str(self.spans[0][n-1]))
        print("Max span sentence is : " + self.get_sentence(0, n-1))

    def get_sentence(self, start, end):
        # print(str(start) + " " + str(end))
        if start==end: return self.sentence[start]
        if self.splits[start][end] == -1:
            return " ".join(x for x in self.sentence[start:end+1])
        return "(" + self.get_sentence(start, self.splits[start][end]) + ")" + "(" + self.get_sentence(self.splits[start][end]+1, end) + ")"