MediumNo. 1191
K-Concatenation Maximum Sum — LeetCode 1191 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given an integer array arr and an integer k, modify the array by repeating it k times. For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
Example
- Input
- arr = [1,2], k = 3
- Output
- 9
Python solution
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
s = mx_pre = mi_pre = mx_sub = 0
for x in arr:
s += x
mx_pre = max(mx_pre, s)
mi_pre = min(mi_pre, s)
mx_sub = max(mx_sub, s - mi_pre)
ans = mx_sub
mod = 10**9 + 7
if k == 1:
return ans % mod
mx_suf = s - mi_pre
ans = max(ans, mx_pre + mx_suf)
if s > 0:
ans = max(ans, (k - 2) * s + mx_pre + mx_suf)
return ans % modComplexity
- Time
- O(n)
- Space · auxiliary
- O(1)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1191. K-Concatenation Maximum Sum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1186 | Maximum Subarray Sum with One Deletion | Medium |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
| 0064 | Minimum Path Sum | Medium |
Frequently asked questions
- How hard is LeetCode 1191. K-Concatenation Maximum Sum?
LeetCode 1191. K-Concatenation Maximum Sum is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1191. K-Concatenation Maximum Sum?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1191. K-Concatenation Maximum Sum?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1191. K-Concatenation Maximum Sum cover?
LeetCode 1191. K-Concatenation Maximum Sum is tagged Array and Dynamic Programming on LeetCode.