K-Concatenation Maximum Sum - Practice Coding Problems

K-Concatenation Maximum Sum - 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].

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.

Input & Output

Example 1 — Basic Positive Array

$ Input: arr = [1,2], k = 3

› Output: 9

💡 Note: The concatenated array is [1,2,1,2,1,2]. The maximum subarray sum is 1+2+1+2+1+2 = 9 (taking the entire array).

Example 2 — Mixed Values

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

› Output: 2

💡 Note: The maximum subarray sum in a single array is max(1, -2, 1, 1-2, -2+1, 1-2+1) = 1. Since total sum is 0, we don't benefit from repetitions.

Example 3 — Single Element

$ Input: arr = [-1], k = 2

› Output: 0

💡 Note: All elements are negative, so the maximum subarray sum is 0 (empty subarray).

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2] with k=3 repetitions

Process

Analyze patterns without full concatenation

Output

Maximum subarray sum is 9

Key Takeaway

🎯 Key Insight: We can solve this efficiently by analyzing three patterns instead of creating the full concatenated array

Asked in

f Facebook 15 G Google 12

The key insight is that instead of generating the full k-concatenated array, we can analyze three patterns: maximum subarray within single array, maximum prefix+suffix across boundaries, and benefits from middle repetitions when total sum is positive. The optimal approach uses pattern analysis achieving Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Pattern Analysis	O(n)	O(1)	Analyze array patterns without generating full concatenation
Brute Force - Generate Full Array	O(n × k)	O(n × k)	Create the full k-concatenated array and apply Kadane's algorithm

Optimized - Pattern Analysis — Algorithm Steps

Step 1: Find max subarray sum in single array using Kadane's
Step 2: Calculate max prefix and suffix sums
Step 3: Handle cases based on k value and array sum
Step 4: Combine patterns optimally

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Patterns

Find max subarray, max prefix, max suffix in single array

Combine Optimally

Consider cross-boundary and middle repetition benefits

Result

Return maximum of all patterns

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long max_ll(long long a, long long b) {
    return a > b ? a : b;
}

int solution(int* arr, int arrSize, int k) {
    if (arrSize == 0 || k == 0) return 0;
    
    const int MOD = 1000000007;
    
    if (k == 1) {
        long long maxSum = 0;
        long long currentSum = 0;
        for (int i = 0; i < arrSize; i++) {
            currentSum = max_ll(0, currentSum + arr[i]);
            maxSum = max_ll(maxSum, currentSum);
        }
        return (int)(maxSum % MOD);
    }
    
    // Find max subarray in single array
    long long maxKadane = 0;
    long long currentSum = 0;
    for (int i = 0; i < arrSize; i++) {
        currentSum = max_ll(0, currentSum + arr[i]);
        maxKadane = max_ll(maxKadane, currentSum);
    }
    
    // Find max prefix sum
    long long maxPrefix = 0;
    currentSum = 0;
    for (int i = 0; i < arrSize; i++) {
        currentSum += arr[i];
        maxPrefix = max_ll(maxPrefix, currentSum);
    }
    
    // Find max suffix sum
    long long maxSuffix = 0;
    currentSum = 0;
    for (int i = arrSize - 1; i >= 0; i--) {
        currentSum += arr[i];
        maxSuffix = max_ll(maxSuffix, currentSum);
    }
    
    long long totalSum = 0;
    for (int i = 0; i < arrSize; i++) {
        totalSum += arr[i];
    }
    
    long long result = max_ll(maxKadane, maxPrefix + maxSuffix);
    
    if (k > 2 && totalSum > 0) {
        long long middleContribution = (long long)(k - 2) * totalSum;
        result = max_ll(result, maxPrefix + middleContribution + maxSuffix);
    }
    
    return (int)(result % MOD);
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int arr[10000];
    int arrSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(arr, arrSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to compute all needed values regardless of k

✓ Linear Growth

Space Complexity

O(1)

Only storing a few variables for sums, no extra arrays needed

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Pattern Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler