Is K-Concatenation Maximum Sum easy or hard?

K-Concatenation Maximum Sum is rated Medium difficulty on LeetCode. The tricky part is realizing that the optimal subarray can span multiple concatenated copies and that Kadane’s algorithm must be adapted instead of constructing the full repeated array.

K-Concatenation Maximum Sum Python/Java solution

Typical implementations apply Kadane’s algorithm with integer accumulation and modular arithmetic for the final result. Python and Java versions iterate through the array once or twice while tracking the current and global maximum sums.

How to solve K-Concatenation Maximum Sum in O(n)?

Compute the maximum subarray using Kadane’s algorithm. Calculate the total sum of the array. If the total sum is positive and k > 1, evaluate the best subarray across two concatenations and add (k-2) times the total sum. Otherwise the answer is simply the best subarray found within one or two copies.

What is the best approach for K-Concatenation Maximum Sum?

Kadane’s Algorithm extension is the most common solution. Run Kadane on one or two copies of the array and use the total array sum to determine whether additional concatenations increase the result. The algorithm runs in O(n) time and O(1) space.

Is K-Concatenation Maximum Sum asked at Google/Amazon/Meta?

This problem follows a classic maximum subarray pattern and variations of it appear in interviews at companies like Amazon, Google, and Meta. Interviewers often expect candidates to recognize Kadane’s algorithm and extend it for repeated arrays.

What data structure is used in K-Concatenation Maximum Sum?

The problem primarily uses arrays and dynamic programming ideas. Kadane’s algorithm maintains running sums while scanning the array, and the prefix-suffix approach uses prefix and suffix sums derived from the same array.

What is the time complexity of K-Concatenation Maximum Sum?

The optimal solutions run in O(n) time where n is the length of the input array. Only a few passes over the array are required to compute the total sum, maximum subarray sum, and prefix or suffix values.

Description Hints 4 Solution Video 22:05

1191. K-Concatenation Maximum Sum

Medium26.5% acceptance1 company

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].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

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

Asked at 1 company

Google

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

How to solve the problem for k=1 ?

Hint 2

Use Kadane's algorithm for k=1.

Hint 3

What are the possible cases for the answer ?

Hint 4

The answer is the maximum between, the answer for k=1, the sum of the whole array multiplied by k, or the maximum suffix sum plus the maximum prefix sum plus (k-2) multiplied by the whole array sum for k > 1.

22:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2]
3

Input

[1,-2,1]
5

Input

[-1,-2]
7

Your code is saved on this device.Solution