数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：求操作后最大子数组的和
假设我们有一个包含整数的数组。我们可以执行一个操作，将数组中`array[i]`的值替换为其平方值；或者`array[i] * array[i]`。只允许进行一次这样的操作，我们必须返回操作后最大可能子数组的和。子数组不能为空。
因此，如果输入类似于`array = [4, 1, -2, -1]`，则输出将为17。
如果我们将`array[0]`的值替换为其平方值，则数组变为`[16, 1, -2, -1]`。由此可以得到最大子数组是`[16, 1]`，其最大和值为16 + 1 = 17。
为了解决这个问题，我们将遵循以下步骤：
- dp1 := 一个新列表，包含负无穷大的值
- dp2 := 一个新列表，包含负无穷大的值
- 对于数组中的每个数字，执行以下操作：
- 在dp1的末尾插入`max((dp1的最后一个元素 + num), num)`
- 在dp2的末尾插入`max((dp1的倒数第二个元素 + num^2), num^2, (dp2的最后一个元素 + num))`
- 返回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]))输入
[4, 1, -2, -1]
输出
17
更新于：2021年10月7日
141 次浏览
广告