在 Python中寻找一个操作后最大子数组的和

假设我们有一个包含整数的数组。我们可以执行一个操作，其中我们可以将数组[i]的值替换为它的平方值；或者数组[i] *数组[i]。只允许一次这样的操作，我们必须返回操作后可能的最大子数组的和。子数组不能为空。

如果输入为 array = [4, 1, -2, -1]，那么输出将是 17。

如果我们用 array[0] 的平方值替换数组中的值，则数组变为 [16, 1, -2, -1]。从中可以得到可能的最大子数组为 [16, 1]，并且它拥有最大的和值 16 + 1 = 17。

为了解决这个问题，我们将执行以下步骤：

dp1 ：一个包含正无穷大值的新列表
dp2 ：一个包含正无穷大值的新列表
对于数组中的每个数字 num，执行以下操作：
- 将 (dp1 的最后一个元素+ num) 和 num 中的最大值插入到 dp1 的末尾
- 将 (dp1 的倒数第二个元素+ num^2)、num^2 和 (dp2 的最后一个元素+ num) 中的最大值插入 dp2 的末尾
返回 dp2 的最大元素

示例

def solve(array):
    dp1 = [float('-inf')]
    dp2 = [float('-inf')]
    for num in array:
        dp1.append(max(dp1[-1] + num, num))
        dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
    return max(dp2)

print(solve([4, 1, -2, -1]))