Python 中对数组进行分区以获得最大和
pythonserver side programmingprogramming更新于 2023/10/5 9:15:00
假设我们有一个整数数组 A，我们必须将数组划分为长度最多为 K 的(连续)子数组。分区后，每个子数组的值都会更改为该子数组的最大值。我们必须在分区后找到给定数组的最大和。因此，如果输入为 [1, 15, 7, 9, 2, 5, 10] 且 k = 3，则输出将为 84。这是因为数组变为 [15, 15, 15, 9, 10, 10, 10]
要解决这个问题，我们将遵循以下步骤 −
- 创建一个长度与 A 相同的数组 dp，并用 0 填充
- 对于 i，范围为 0 到 A 的长度 - 1
- dp[i] = A[i] + dp[i - 1] if i – 1 >= 0 else 0
- temp := A[i]
- 对于 j，范围为 1 到 k – 1
- 如果 i – j >= 0
- index := i – j
- temp := temp 和 A[i - j] 的最大值
- 如果 index – 1 >= 0，则
- dp[i] := dp[i] 和 (temp*(i – index + 1) + dp[index - 1]) 的最大值
- 否则 dp[i] := dp[i] 和 0 的最大值
- 如果 i – j >= 0
- 返回 dp 的最后一个元素
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object): def maxSumAfterPartitioning(self, A, K): dp = [0 for i in range(len(A))] for i in range(len(A)): dp[i] = A[i] + (dp[i-1] if i-1>=0 else 0) temp = A[i] for j in range(1,K): if i-j>=0: index = i-j temp = max(temp,A[i-j]) dp[i] = max(dp[i],temp*(i-index+1) + (dp[index-1] if index-1 >=0 else 0)) return dp[-1] ob = Solution() print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10],3))
输入
[1,15,7,9,2,5,10] 3
输出
84
