链接：httpsacnowcodercomacmcontest60456B来源：牛客网小红拿到了一个数组每个数字被染成了红色或蓝色。小红有很多次操作每次操作可以选择两个相邻的不同颜色的数字标记并获得它们数字之和的得分。已经被标记的数字无法再次标记。小红想知道自己最多能获得多少分。

解题思路： 首先，我们可以观察到，只有相邻的不同颜色的数字才能进行标记，所以我们可以将数组中的相邻的相同颜色的数字合并成一个数字，只保留不同颜色的数字。

然后，我们可以使用动态规划的思想来解决这个问题。我们定义一个二维数组dp，其中dp[i][j]表示从第i个数字到第j个数字能够获得的最大得分。数组的大小为n*n，其中n表示不同颜色的数字的个数。

接下来，我们可以使用一个循环来遍历数组，从长度为2的子数组开始，依次计算dp[i][j]的值。具体的计算方法如下： 对于dp[i][j]，我们可以遍历i到j之间的每一个位置k，计算dp[i][j]的最大值。假设我们选择标记数字k和数字k+1，那么dp[i][j]的值就等于dp[i][k-1]+dp[k+2][j]+nums[k]+nums[k+1]，其中dp[i][k-1]表示从第i个数字到第k-1个数字能够获得的最大得分，dp[k+2][j]表示从第k+2个数字到第j个数字能够获得的最大得分，nums[k]和nums[k+1]分别表示数字k和数字k+1的值。

最后，dp[0][n-1]就表示从第0个数字到第n-1个数字能够获得的最大得分。

代码实现如下：

def maxScore(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+2][j] + nums[k] + nums[k+1])

    return dp[0][n-1]

时间复杂度分析： 由于需要计算dp数组中的每一个元素，所以时间复杂度为O(n^3)，其中n为不同颜色的数字的个数