Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1043 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1043 # by problem number
lcpy gen -s partition_array_for_maximum_sum # by problem name
arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Input: arr = [1], k = 1
Output: 1
1 <= arr.length <= 5000 <= arr[i] <= 10^91 <= k <= arr.lengthclass Solution:
# Time: O(n * k)
# Space: O(n)
def max_sum_after_partitioning(self, arr: list[int], k: int) -> int:
n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
best = 0
mx = 0
for length in range(1, min(k, i) + 1):
mx = max(mx, arr[i - length])
best = max(best, dp[i - length] + mx * length)
dp[i] = best
return dp[n]
| Time | Space |
|---|---|
| O(n * k) | O(n) |