Problem Explanation

Given an integer array, we are required to repeat the array k times, and then find the maximum sub-array sum in the modified array. If in case, the sub-array length is 0, its sum is taken as 0.

The solution needs to be returned with a modulo value of 10^9 + 7, as the array sum could become very large.

Let's understand this with an example. Suppose we have an array arr = [1,2] and k value as 3. As per the problem, the array gets repeated 3 times and becomes [1,2,1,2,1,2]. The maximum sub-array sum in this case would be the sum of the entire array which is 9.

Approach

We can solve this problem using Kadane's algorithm, which is used to find the maximum sum of a contiguous subarray in an array with a time complexity of O(n). The original Kadane's algorithm assumes that there's at least one positive number, but we can modify it for this problem to handle all negative numbers by initializing the maximum sum as 0.

The main idea is to calculate the maximum subarray sum in the 1st and 2nd array and then, if the total sum of the original array is greater than 0 and k > 2, we add (sum of array) * (k - 2).

Example

For array arr = [1,-2,1] and k value as 5, the maximum sub-array sum would be 2. The sequence goes as: [1, -2, 1, 1, -2, 1, 1, -2, 1, 1, -2]. The maximum sub-array sum would be from the sub-array [1, 1] after the third repetition of the original array.

Now, let's see the solutions in Python, Java, JavaScript, C++, and C#.

Python

1
2python
3class Solution:
4  def kConcatenationMaxSum(self, arr, k):
5    kMod = 10**9 + 7
6    sz = len(arr) * (1 if k == 1 else 2)
7    sumArr = sum(arr)
8    return (self.kadane(arr, sz) + sumArr * (k - 2)) % kMod if sumArr > 0 and k > 2 else self.kadane(arr, sz) % kMod
9
10  def kadane(self, A, sz):
11    ans = 0
12    sumArr = 0
13    for i in range(sz):
14      a = A[i % len(A)]
15      sumArr = max(a, sumArr + a)
16      ans = max(ans, sumArr)
17    return ans 

Java

1
2java
3import java.util.stream.IntStream;
4
5public class Solution {
6    public int kConcatenationMaxSum(int[] arr, int k) {
7        int MOD = 1_000_000_007;
8        int sz = arr.length * (k == 1 ? 1 : 2);
9        int sum = IntStream.of(arr).sum();
10        return (int) ((sum > 0 && k > 2 ? kadane(arr, sz) + ((long) sum * (k - 2)) : kadane(arr, sz)) % MOD);
11    }
12
13    private long kadane(int[] arr, int sz) {
14        long ans = 0;
15        long sum = 0;
16        for (int i = 0; i < sz; i++) {
17            int a = arr[i % arr.length];
18            sum = Math.max(a, sum + a);
19            ans = Math.max(ans, sum);
20        }
21        return ans;
22    }
23}

JavaScript

1
2javascript
3var kConcatenationMaxSum = function(arr, k) {
4    let max = maxSubarraySum = maxPrefixSum = prefixSum = 0;
5    let maxSuffixSum = suffixSum = 0;
6    let MOD = 1e9 + 7;
7    for (let i of arr) {
8        prefixSum += i;
9        maxPrefixSum = Math.max(maxPrefixSum, prefixSum);
10        suffixSum += arr[arr.length - 1 - i];
11        maxSuffixSum = Math.max(maxSuffixSum, suffixSum);
12        maxSubarraySum = Math.max(maxSubarraySum + i, i);
13        max = Math.max(max, maxSubarraySum);
14    }
15    let sum = prefixSum;
16    if (k > 1) {
17        max = Math.max(max, maxPrefixSum + (sum * (k - 2)) % MOD + maxSuffixSum);
18        max = Math.max(max, maxPrefixSum + (sum * (k - 1)) % MOD);
19    }
20    return max % MOD;
21};

C++

1
2c++
3#include <algorithm>
4#include <numeric>
5#include <vector>
6
7class Solution {
8public:
9    int kConcatenationMaxSum(std::vector<int>& arr, int k) {
10        const int MOD = 1'000'000'007;
11        const int sz = arr.size() * (k == 1 ? 1 : 2);
12        const int overall_sum = std::accumulate(arr.begin(), arr.end(), 0);
13        return (overall_sum > 0 && k > 2 ? kadane(arr, sz) + static_cast<long long>(overall_sum) * (k - 2) : kadane(arr, sz)) % MOD;
14    }
15
16private:
17    long long kadane(const std::vector<int>& arr, int sz) {
18        long long maxSum = 0;
19        long long sum = 0;
20        for (int i = 0; i < sz; ++i) {
21            const int a = arr[i % arr.size()];
22            sum = std::max<int>(a, sum + a);
23            maxSum = std::max<unsigned long long>(maxSum, sum);
24        }
25        return maxSum;
26    }
27};

C#

1
2csharp
3using System.Linq;
4
5public class Solution {
6    public int KConcatenationMaxSum(int[] arr, int k) {
7        int MOD = 1_000_000_007;
8        int sz = arr.Length * (k == 1 ? 1 : 2);
9        int sum = arr.Sum();
10        return (int) ((sum > 0 && k > 2 ? kadane(arr, sz) + ((long) sum * (k - 2)) : kadane(arr, sz)) % MOD);
11    }
12
13    private long kadane(int[] arr, int sz) {
14        long ans = 0;
15        long sum = 0;
16        for (int i = 0; i < sz; i++) {
17            int a = arr[i % arr.Length];
18            sum = Math.Max(a, sum + a);
19            ans = Math.Max(ans, sum);
20        }
21        return ans;
22    }
23}

From the above solutions, we can observe that the solutions follow the same logic in all languages. They are implemented by using Kadane's algorithm. We start by initialising the maximum answer as 0 and then check for each element, if the sum of the current element and the previous sum are greater than the current element or not. If it's greater, we update the sum and then update the answer if it's greater than the current answer. Finally, we return the answer.In conclusion, the methods explained above to solve the maximum sub-array sum problem are simple yet effective. In all of the presented languages - Python, Java, JavaScript, C++, and C# - the solution leverages Kadane's algorithm. It starts by initializing the maximum sum obtained from a sub-array as 0, and then iterates through each element of the array, checking if the sum of the current element and the previous sum is greater than the current element. If it is, the sum is updated. If the sum is greater than the current maximum sum, the maximum sum is updated. This process is repeated until all elements in the array have been assessed.

Although the syntax may differ from one language to another, the fundamental logic remains the same. It is important to note that the modulo operation is used to ensure the result doesn't exceed the maximum integer that can be stored. Therefore, it also proves that even though the coding principles remain the same, understanding the nuances of each programming language is crucial for implementation.

Lastly, the solutions provided demonstrate that having a solid foundation in algorithms and data structures is essential in competitive programming and problem-solving interviews, regardless of which language one codes in. Understanding the functioning and application of Kadane's algorithm is an added advantage when solving array-based problems.