What is the key pattern in solving the K-Concatenation Maximum Sum?

The key pattern involves dynamic programming with state transitions, utilizing prefix and suffix sums for larger values of k.

How do we solve for k=1 in the K-Concatenation Maximum Sum problem?

For k=1, we find the maximum sub-array sum in the original array using algorithms like Kadane's or dynamic programming.

Why do we need to handle both prefix and suffix sums?

Prefix and suffix sums help maximize the sub-array sum when the array is repeated k times, especially for large k values.

What is the expected time complexity for large k in this problem?

The time complexity is O(n) for calculating prefix and suffix sums, and O(1) for combining them to handle large k values efficiently.

How does GhostInterview help with solving dynamic programming problems like this?

GhostInterview walks you through key dynamic programming patterns and scaling techniques, enhancing problem-solving efficiency.

#1191

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

K 次串联后最大子数组之和

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0 ，在这种情况下它的总和也是 0 。由于…

数组动态规划

题目描述

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回结果对 10⁹ + 7 取模。

示例 1：

输入：arr = [1,2], k = 3
输出：9

示例 2：

输入：arr = [1,-2,1], k = 5
输出：2

示例 3：

输入：arr = [-1,-2], k = 7
输出：0

提示：

1 <= arr.length <= 10⁵
1 <= k <= 10⁵
-10⁴ <= arr[i] <= 10⁴

lightbulb

解题思路

方法一：前缀和 + 分类讨论

我们记数组 $arr$ 所有元素之和为 $s$ ，最大前缀和为 $mxPre$ ，最小前缀和为 $miPre$ ，最大子数组和为 $mxSub$ 。

遍历数组 $arr$ ，对于每个元素 $x$ ，我们更新 $s = s + x$ , $mxPre = \max(mxPre, s)$ , $miPre = \min(miPre, s)$ , $mxSub = \max(mxSub, s - miPre)$ 。

接下来，我们考虑 $k$ 的取值情况：

当 $k = 1$ 时，答案为 $mxSub$ 。
当 $k \ge 2$ 时，如果最大子数组横跨两个 $arr$ ，那么答案为 $mxPre + mxSuf$ ，其中 $mxSuf = s - miPre$ 。
当 $k \ge 2$ 且 $s > 0$ 时，如果最大子数组横跨三个 $arr$ ，那么答案为 $(k - 2) \times s + mxPre + mxSuf$ 。

最后，我们返回答案对 $10^9 + 7$ 取模的结果。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $arr$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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 % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate handle the k=1 base case effectively?
question_mark
Does the candidate recognize the importance of prefix and suffix sums for larger k?
question_mark
How efficiently does the candidate scale the solution for large k values?

warning

常见陷阱

外企场景

error
Forgetting to handle the case where the sub-array sum is zero.
error
Not properly combining the prefix and suffix sums when k > 1.
error
Inefficient solutions that do not scale for large values of k.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What happens if we reduce k to 1? How does the solution change?
arrow_right_alt
Can this approach be used for negative numbers in the array?
arrow_right_alt
How would you handle cases where all elements in the array are negative?

help

常见问题

外企场景

继续练习

#1187 使数组严格递增 #1186 删除一次得到子数组最大和 #1218 最长定差子序列