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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K-Concatenation Maximum Sum

Difficulty: Medium

Problem Description

Given an integer array arr and an integer k, modify the array by repeating it k times. 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^9 + 7.

Key Insights

  • The problem requires us to find the maximum sub-array sum from a modified array created by repeating the original array k times.
  • Directly constructing the modified array can lead to excessive memory usage, especially when k is large.
  • The maximum sub-array sum can be computed using Kadane's algorithm.
  • The sum of the entire array is crucial for handling cases where k > 2, as it can affect the maximum sum when added multiple times.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves using Kadane's algorithm to find the maximum sub-array sum in the original array. We also need to consider the total sum of the array and the maximum prefix and suffix sums to deal with cases where the modified array consists of multiple repetitions.

  1. Compute the maximum sub-array sum using Kadane's algorithm.
  2. Calculate the total sum of the array.
  3. If k = 1, return the maximum sub-array sum directly.
  4. If k = 2, consider the maximum sum that can be obtained by combining the original array and its prefix/suffix sums.
  5. If k > 2, check if the total sum is positive. If it is, include it in the sum of prefix and suffix to maximize the overall sum.

Code Solutions

def kConcatenationMaxSum(arr, k):
    MOD = 10**9 + 7
    
    def kadane(arr):
        max_sum = 0
        current_sum = 0
        for num in arr:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        return max_sum
    
    max_subarray_sum = kadane(arr)
    total_sum = sum(arr)
    max_prefix_sum = current_prefix_sum = 0
    max_suffix_sum = current_suffix_sum = 0
    
    for num in arr:
        current_prefix_sum += num
        max_prefix_sum = max(max_prefix_sum, current_prefix_sum)
    
    for num in reversed(arr):
        current_suffix_sum += num
        max_suffix_sum = max(max_suffix_sum, current_suffix_sum)
    
    if k == 1:
        return max_subarray_sum % MOD
    elif k == 2:
        return max(max_subarray_sum, max_prefix_sum + max_suffix_sum) % MOD
    else:
        if total_sum > 0:
            return max(max_subarray_sum, max_prefix_sum + max_suffix_sum + total_sum * (k - 2)) % MOD
        else:
            return max(max_subarray_sum, max_prefix_sum + max_suffix_sum) % MOD
← Back to All Questions