1191. K-Concatenation Maximum Sum
Problem Description
The problem deals with finding the maximum sum of a sub-array within a modified array, which is the result of repeating the original integer array arr
a total of k
times. The challenge involves not just the repetition of the array but computing the maximum possible sum of a contiguous sub-array. This includes the possibility of a sub-array having a length of 0
, which would correspond to a sum of 0
.
Intuition
To tackle this problem, we need to understand a few important concepts:
-
Kadane's Algorithm: This algorithm is used for finding the maximum sum of a contiguous sub-array within a single unmodified array. It does this by looking for all positive contiguous segments of the array (max_ending_here) and keeping track of the maximum sum contiguous segment among all positive segments (max_so_far). The algorithm increments the sum when the running sum is positive, and resets it to zero when the running sum becomes negative.
-
Prefix Sum and Suffix Sum: The prefix sum is the sum of elements from the start of the array up to a certain index, and the suffix sum is the sum of elements from a certain index to the end of the array. These can be useful when handling repeated arrays, as the maximum sum can span across the boundary between two repeated segments.
Considering these concepts, the intuition for the solution approach can be broken down into steps:
- The
Kadane's Algorithm
is used to find the maximum sum of a contiguous sub-array from the originalarr
. - The sum of the entire array (
s
) is calculated to be used in checking if we can increase the maximum sum by including sums from multiple repetitions ofarr
. - We find the maximum prefix sum (
mx_pre
), i.e., the largest sum obtained from the start of an array up to any index. - We find the maximum suffix sum (
mx_suf
), i.e., the largest sum that starts at any index and goes to the end of an array. - Based on the value of
k
, we decide how to combine these sums to compute the final answer:- If
k
is equal to 1, the maximum sub-array sum is only within the single original array and it's the result obtained fromKadane's Algorithm
. - If
k
is greater than 1 and the total sum of the array (s
) is positive, the maximum sum could potentially span across the middle arrays completely, so we consider the array sum multiplied by (k-2) and add both the maximum prefix and suffix sums. - If
k
is greater than 1 and the total sum of the array is non-positive, we just need to consider the maximum prefix and suffix sums, as spanning across copies would not increase the overall sub-array sum.
- If
Finally, since the answer can be very large, we return the result modulo 10^9 + 7
to ensure it stays within the integer limits for the problem.
Learn more about Dynamic Programming patterns.
Solution Approach
In the provided solution, the implementation walks through the array and applies the concepts mentioned in the Intuition section.
Here's a breakdown of the logic used:
-
Initialization: We start by initializing variables to store the sum of the array (
s
), the maximum prefix sum (mx_pre
), the minimum prefix sum (mi_pre
), and the maximum sub-array sum (mx_sub
). -
Single Pass for Kadane's Algorithm and Prefix Sums:
- We loop through each element in
arr
:- Update the sum of the array (
s
) by adding the current elementx
. - Update the maximum prefix sum (
mx_pre
) to the maximum ofmx_pre
and the current sums
. - Update the minimum prefix sum (
mi_pre
) to the minimum ofmi_pre
and the current sums
. - Update the maximum sub-array sum (
mx_sub
) to the maximum of the currentmx_sub
and the difference between the current sums
and the minimum prefix sum (mi_pre
), which represents Kadane's algorithm execution for the sub-array ending at the current element.
- Update the sum of the array (
- We loop through each element in
-
Handling Multiple Concatenations:
- After the loop, we calculate the suffix maximum sum (
mx_suf
) by subtracting the minimum prefix sum (mi_pre
) from the total sum of the array (s
). - The base answer variable
ans
is initialized with the value obtained from Kadane's Algorithm (mx_sub
). - If
k
equals 1, which means the array is not concatenated, we use the answer gotten from the Kadane's pass earlier and return it modulo10^9 + 7
. - For the case where
k
is greater than 1, we explore the options by combining different parts of the array:- First, we use the maximum prefix sum plus the maximum suffix sum (
mx_pre + mx_suf
) and updateans
if this is greater than the currentans
. - Next, if the sum of the array (
s
) is positive, we explore the possibility that the maximum sum spans across the entire middle part of the concatenated array. This leads us to consider(k - 2) * s + mx_pre + mx_suf
. We then again updateans
if this is greater than the currentans
.
- First, we use the maximum prefix sum plus the maximum suffix sum (
- After the loop, we calculate the suffix maximum sum (
-
Returning the Result:
- In the final step, we return the answer
ans
modulo10^9 + 7
.
- In the final step, we return the answer
This approach effectively handles the possibility of maximizing the sub-array sum by including the sum of the entire array when it is beneficial (i.e., when the total sum is positive) due to the concatenation specified by k
. It ensures that the maximum sub-array sum is found even if it spans across multiple copies of the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach:
Suppose our given array is arr = [3, -1, 2]
and k = 2
. That means we need to find the maximum sub-array sum in an array that would look like [3, -1, 2, 3, -1, 2]
after concatenating arr
to itself once (as k = 2
).
-
Initialization:
s
= 0 (sum of the array)mx_pre
= 0 (maximum prefix sum)mi_pre
= 0 (minimum prefix sum)mx_sub
= 0 (maximum sub-array sum)
-
Single Pass for Kadane's Algorithm and Prefix Sums:
- For the first element
3
:s
=3
mx_pre
=3
mi_pre
=0
mx_sub
=3
- For the second element
-1
:s
=3 - 1
=2
mx_pre
remains3
mi_pre
remains0
mx_sub
remains3
- For the third element
2
:s
=2 + 2
=4
mx_pre
=4
mi_pre
remains0
mx_sub
=4
(since4
-0
>3
)
- For the first element
-
Handling Multiple Concatenations:
- After the loop, we calculate
mx_suf
which iss - mi_pre
=4 - 0
=4
. - The base answer
ans
ismx_sub
which is currently4
. - Since
k > 1
, we examine the maximum sum using concatenation:- We calculate
mx_pre + mx_suf
=4 + 4
=8
and compare it withans
, thusans
becomes8
. - Since the sum of the array
s
is positive, we explore the maximum sum crossing the entire middle part which would be(k - 2) * s + mx_pre + mx_suf
. Sincek = 2
, multiplying byk - 2
equals0
, so this step does not changeans
.
- We calculate
- After the loop, we calculate
-
Returning the Result:
- The function would return
ans
modulo10^9 + 7
, which is8
in this case, as the maximum sum sub-array is[3, -1, 2, 3, -1, 2]
itself whenk = 2
, with the sum being8
.
- The function would return
This example demonstrates that even when our given array has negative numbers, by strategically utilizing the concatenation of the array k
times, we can maximize the sub-array sum without including the negative sub-arrays. The technique of combining prefix and suffix sums with Kadane's algorithm and handling different cases based on the total sum s
and the count k
leads to a comprehensive solution.
Solution Implementation
1from typing import List
2
3class Solution:
4 def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
5 # Initialize variables
6 total_sum = max_prefix = min_prefix = max_subarray_sum = 0
7
8 # Calculate max subarray sum for a single array iteration
9 for num in arr:
10 total_sum += num
11 max_prefix = max(max_prefix, total_sum)
12 min_prefix = min(min_prefix, total_sum)
13 max_subarray_sum = max(max_subarray_sum, total_sum - min_prefix)
14
15 # The result after a single iteration
16 result = max_subarray_sum
17 mod = 10**9 + 7
18
19 # If k is 1, return the result of a single array's max subarray sum
20 if k == 1:
21 return result % mod
22
23 # Calculate the maximum suffix sum for potential use in concatenated arrays
24 max_suffix = total_sum - min_prefix
25
26 # Update result for potential double array combination
27 result = max(result, max_prefix + max_suffix)
28
29 # If the array sum is positive, calculate the max sum when array is concatenated k times
30 if total_sum > 0:
31 result = max(result, ((k - 2) * total_sum) + max_prefix + max_suffix)
32
33 return result % mod # Return the result modulo the provided modulus
34
1class Solution {
2
3 // Computes the maximum sum of a subsequence in an array that can be achieved by
4 // concatenating the array k times.
5 public int kConcatenationMaxSum(int[] arr, int k) {
6 long sum = 0; // Total sum of the array elements.
7 long maxPrefixSum = 0; // Maximum prefix sum found so far.
8 long minPrefixSum = 0; // Minimum prefix sum found so far.
9 long maxSubarraySum = 0; // Maximum subarray sum found so far.
10
11 // Iterate over the array to find the maximum subarray sum, maximum prefix,
12 // and minimum prefix sums.
13 for (int value : arr) {
14 sum += value;
15 maxPrefixSum = Math.max(maxPrefixSum, sum);
16 minPrefixSum = Math.min(minPrefixSum, sum);
17 maxSubarraySum = Math.max(maxSubarraySum, sum - minPrefixSum);
18 }
19
20 long answer = maxSubarraySum; // This holds the result, which is initialized to maxSubarraySum.
21 final int mod = (int) 1e9 + 7; // Module to perform the answer under modulo operation.
22
23 // If there's only one concatenation, simply return the max subarray sum modulo mod.
24 if (k == 1) {
25 return (int) (answer % mod);
26 }
27
28 long maxSuffixSum = sum - minPrefixSum; // Maximum suffix sum after one traversal.
29
30 // Check if adding the entire array sum (suffix and prefix) is better.
31 answer = Math.max(answer, maxPrefixSum + maxSuffixSum);
32
33 // If the sum of the array is positive, the best option might be to take the sum k-2 times,
34 // then add the maxPrefix and maxSuffix sums.
35 if (sum > 0) {
36 answer = Math.max(answer, (k - 2) * sum + maxPrefixSum + maxSuffixSum);
37 }
38
39 // Return the maximal sum found under modulo mod.
40 return (int) (answer % mod);
41 }
42}
43
1class Solution {
2public:
3 int kConcatenationMaxSum(vector<int>& arr, int k) {
4 long sumOfArray = 0, maxPrefixSum = 0, minPrefixSum = 0, maxSubarraySum = 0;
5 const int MOD = 1e9 + 7; // Define the modulus for the answer
6
7 // Calculate the maximum subarray sum for one array
8 for (int num : arr) {
9 sumOfArray += num; // Sum of elements so far
10 maxPrefixSum = max(maxPrefixSum, sumOfArray); // Max sum from the start to current
11 minPrefixSum = min(minPrefixSum, sumOfArray); // Min sum from the start to current
12 maxSubarraySum = max(maxSubarraySum, sumOfArray - minPrefixSum); // Kadane's algorithm update
13 }
14
15 long result = maxSubarraySum; // Initialize the result with max subarray sum
16
17 // Handle the case when the array is concatenated only once
18 if (k == 1) {
19 return result % MOD;
20 }
21
22 long maxSuffixSum = sumOfArray - minPrefixSum; // Sum of max suffix
23 result = max(result, maxPrefixSum + maxSuffixSum); // Max of result and sum of max prefix and suffix
24
25 // If the sum of the array is positive, we can take the whole arrays k-2 times along with maxPrefix and maxSuffix
26 if (sumOfArray > 0) {
27 result = max(result, maxPrefixSum + (k - 2) * sumOfArray + maxSuffixSum);
28 }
29
30 // Return the result modulo 10^9 + 7
31 return result % MOD;
32 }
33};
34
1const MOD: number = 1e9 + 7; // Define the modulus for the answer
2
3function kConcatenationMaxSum(arr: number[], k: number): number {
4 let sumOfArray: number = 0, maxPrefixSum: number = 0, minPrefixSum: number = 0, maxSubarraySum: number = 0;
5
6 // Calculate the maximum subarray sum for one array
7 for (const num of arr) {
8 sumOfArray = (sumOfArray + num) % MOD; // Keep updating the sum of elements
9 maxPrefixSum = Math.max(maxPrefixSum, sumOfArray); // Max sum from start to current position
10 minPrefixSum = Math.min(minPrefixSum, sumOfArray); // Min sum from start to current position
11 maxSubarraySum = Math.max(maxSubarraySum, (sumOfArray - minPrefixSum + MOD) % MOD); // Kadane's algorithm update
12 }
13
14 let result: number = maxSubarraySum; // Initialize the result with max subarray sum
15
16 // Handle the case when the array is concatenated only once
17 if (k === 1) {
18 return result;
19 }
20
21 let maxSuffixSum: number = (sumOfArray - minPrefixSum + MOD) % MOD; // Sum of the max suffix
22 result = Math.max(result, (maxPrefixSum + maxSuffixSum) % MOD); // Max of result and the sum of max prefix and max suffix
23
24 // If the sum of the array is positive, we include the whole arrays (k - 2) times along with maxPrefix and maxSuffix
25 if (sumOfArray > 0) {
26 result = Math.max(result, (maxPrefixSum + ((k - 2) * sumOfArray + maxSuffixSum) % MOD) % MOD);
27 }
28
29 // Return the result modulo 10^9 + 7
30 return result;
31}
32
Time and Space Complexity
The given Python code defines a method kConcatenationMaxSum
which finds the maximum sum of a subarray in the K-concatenated array formed by repeating the given array k
times.
Time Complexity
The function iterates once through the array arr
, performing a constant amount of work in each iteration, including finding maximum and minimum prefixes, and computing the maximum subarray sum ending at any element. Therefore, the time complexity of iterating the array is O(n)
where n
is the length of arr
.
After this iteration, there is a constant amount of work done to compute mx_suf
and the maximum of ans
, mx_pre + mx_suf
, and (k - 2) * s + mx_pre + mx_suf
if s > 0
. These operations take O(1)
time.
Hence, the overall time complexity of the function is O(n + 1)
, which simplifies to O(n)
.
Space Complexity
In terms of space, the function allocates a few variables (s
, mx_pre
, mi_pre
, mx_sub
, and mod
), which use O(1)
space as their number does not scale with the input size.
The inputs arr
and k
are used without any additional space being allocated that depends on their size (no extra arrays or data structures are created). Thus, the space used is constant.
As such, the space complexity is O(1)
.
Combining the analysis above, the code has a linear time complexity and constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.