We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-Concatenation Maximum Sum

Number: 1299

Difficulty: Medium

Paid? No

Companies: Adobe

Problem Description

Given an integer array arr and an integer k, repeat the array k times to form a new array and return the maximum sub-array sum of this concatenated array. Note that the sub-array may be empty (with sum 0), and since the answer can be very large, return the result modulo 10^9+7.

Key Insights

  • Use Kadane's algorithm to determine the maximum subarray sum for one copy of the array.
  • Calculate the total sum of the original array.
  • For k >= 2, compute the maximum prefix sum (maximum sum starting at index 0) and the maximum suffix sum (maximum sum ending at the last index).
  • If the total sum of the array is positive, then adding (k-2) full copies (i.e. total sum multiplied by k-2) between the suffix and prefix can boost the maximum sum.
  • Always consider the possibility of an empty subarray (0) if all numbers are negative.

Space and Time Complexity

Time Complexity: O(n), where n is the length of arr (iterating a few times over arr). Space Complexity: O(1), using only a few extra variables.

Solution

The solution uses Kadane's algorithm to find the maximum subarray sum in one copy of the array. For k > 1, the idea is to connect the end of one copy with the beginning of the next copy by computing the maximum prefix sum and maximum suffix sum. If the total sum of arr is positive, then the optimal result might span across multiple copies: suffix from the first copy + (k-2 copies worth of total sum) + prefix from the last copy. The final answer is the maximum of this combined sum and the maximum subarray sum within one or two concatenated copies. Finally, return the result modulo 10^9+7.

Code Solutions

MOD = 10**9 + 7

def kConcatenationMaxSum(arr, k):
    n = len(arr)
    # Step 1: Find maximum subarray sum for one copy using Kadane's Algorithm.
    max_ending_here = 0
    max_subarray = 0  # Consider empty subarray with sum 0.
    for a in arr:
        max_ending_here = max(0, max_ending_here + a)
        max_subarray = max(max_subarray, max_ending_here)
    
    # If there is only one repetition, return the result.
    if k == 1:
        return max_subarray % MOD

    # Step 2: Compute total sum, maximum prefix sum, and maximum suffix sum.
    total_sum = sum(arr)
    
    # Maximum prefix sum: maximum sum from the beginning of the array.
    prefix_sum = 0
    prefix_max = float('-inf')
    for a in arr:
        prefix_sum += a
        prefix_max = max(prefix_max, prefix_sum)
    
    # Maximum suffix sum: maximum sum from the end of the array.
    suffix_sum = 0
    suffix_max = float('-inf')
    for a in reversed(arr):
        suffix_sum += a
        suffix_max = max(suffix_max, suffix_sum)
    
    # Calculate maximum sum based on total_sum.
    if total_sum > 0:
        result = max(prefix_max + suffix_max + (k - 2) * total_sum, max_subarray)
    else:
        result = max(prefix_max + suffix_max, max_subarray)
    
    return result % MOD
← Back to All Questions