K Concatenation Maximum Sum - Leetcode Solution

The K Concatenation Maximum Sum problem on LeetCode is as follows:

Given an array arr of positive integers and an integer k, you need to find the maximum sum of the subarray containing at most k contiguous concatenations of arr. Return the maximum sum.

A concatenation of an array is defined as the process of joining two arrays end-to-end. For example, [1,2] + [2,3] = [1,2,2,3].

To solve this problem, we can use Kadane's algorithm to find the maximum subarray sum of one concatenation of arr. Then, we can calculate the sum of all elements in arr and multiply it by k-2. Finally, we can check whether the maximum subarray sum of two concatenations of arr is greater than zero, and add it to the total sum if it is.

Here is a detailed solution:

1. Calculate the maximum subarray sum of one concatenation of arr using Kadane's algorithm:

def maxSubArraySum(arr):
    max_sum = arr[0]
    curr_sum = arr[0]
    for i in range(1, len(arr)):
        curr_sum = max(arr[i], curr_sum + arr[i])
        max_sum = max(max_sum, curr_sum)
    return max_sum

max_sum_one_concatenation = maxSubArraySum(arr)

2. Calculate the sum of all elements in arr and multiply it by k-2:

total_sum = sum(arr)
max_sum_k_concatenations = max(max_sum_one_concatenation, 0) + total_sum * (k-2)

3. Check whether the maximum subarray sum of two concatenations of arr is greater than zero, and add it to the total sum if it is:

if k > 1:
    max_sum_two_concatenations = maxSubArraySum(arr + arr)
    if max_sum_two_concatenations > 0:
        max_sum_k_concatenations += max_sum_two_concatenations * (k-2)

4. Return the maximum sum:

return max_sum_k_concatenations

The complete solution looks like this:

def maxSubArraySum(arr):
    max_sum = arr[0]
    curr_sum = arr[0]
    for i in range(1, len(arr)):
        curr_sum = max(arr[i], curr_sum + arr[i])
        max_sum = max(max_sum, curr_sum)
    return max_sum

def kConcatenationMaxSum(arr, k):
    max_sum_one_concatenation = maxSubArraySum(arr)
    total_sum = sum(arr)
    max_sum_k_concatenations = max(max_sum_one_concatenation, 0) + total_sum * (k-2)
    if k > 1:
        max_sum_two_concatenations = maxSubArraySum(arr + arr)
        if max_sum_two_concatenations > 0:
            max_sum_k_concatenations += max_sum_two_concatenations * (k-2)
    return max_sum_k_concatenations

1