1191. K-Concatenation Maximum Sum LeetCode Solution

In this guide, you will get 1191. K-Concatenation Maximum Sum LeetCode Solution with the best time and space complexity. The solution to K-Concatenation Maximum Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
K-Concatenation Maximum Sum solution in C++
K-Concatenation Maximum Sum solution in Java
K-Concatenation Maximum Sum solution in Python
Additional Resources

1191. K-Concatenation Maximum Sum LeetCode Solution image

Problem Statement of K-Concatenation Maximum Sum

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 109 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

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

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

1 <= arr.length <= 105
1 <= k <= 105
-104 <= arr[i] <= 104

Complexity Analysis

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

1191. K-Concatenation Maximum Sum LeetCode Solution in C++

class Solution {
 public:
  int kConcatenationMaxSum(vector<int>& arr, int k) {
    constexpr int kMod = 1'000'000'007;
    const int sz = arr.size() * (k == 1 ? 1 : 2);
    const int sum = accumulate(arr.begin(), arr.end(), 0);
    // The concatenated array will be [arr1, arr2, ..., arrk].
    // If sum(arr) > 0 and k > 2, then arr2, ..., arr(k - 1) should be included.
    // Equivalently, maxSubarraySum is from arr1 and arrk.
    return (sum > 0 && k > 2 ? kadane(arr, sz) + sum * static_cast<long>(k - 2)
                             : kadane(arr, sz)) %
           kMod;
  }

 private:
  int kadane(const vector<int>& arr, int sz) {
    int ans = 0;
    int sum = 0;
    for (int i = 0; i < sz; ++i) {
      const int a = arr[i % arr.size()];
      sum = max(a, sum + a);
      ans = max(ans, sum);
    }
    return ans;
  }
};
/* code provided by PROGIEZ */

1191. K-Concatenation Maximum Sum LeetCode Solution in Java

class Solution {
  public int kConcatenationMaxSum(int[] arr, int k) {
    final int kMod = 1_000_000_007;
    final int sz = arr.length * (k == 1 ? 1 : 2);
    final int sum = Arrays.stream(arr).sum();
    // The concatenated array will be [arr1, arr2, ..., arrk].
    // If sum(arr) > 0 and k > 2, then arr2, ..., arr(k - 1) should be included.
    // Equivalently, maxSubarraySum is from arr1 and arrk.
    if (sum > 0 && k > 2)
      return (int) ((kadane(arr, sz) + sum * (long) (k - 2)) % kMod);
    return kadane(arr, sz) % kMod;
  }

  private int kadane(int[] arr, int sz) {
    int ans = 0;
    int sum = 0;
    for (int i = 0; i < sz; ++i) {
      final int a = arr[i % arr.length];
      sum = Math.max(a, sum + a);
      ans = Math.max(ans, sum);
    }
    return ans;
  }
}
// code provided by PROGIEZ

1191. K-Concatenation Maximum Sum LeetCode Solution in Python

class Solution:
  def kConcatenationMaxSum(self, arr: list[int], k: int) -> int:
    kMod = 1_000_000_007
    sz = len(arr) * (1 if k == 1 else 2)
    summ = sum(arr)
    # The concatenated array will be [arr1, arr2, ..., arrk].
    # If sum(arr) > 0 and k > 2, then arr2, ..., arr(k - 1) should be included.
    # Equivalently, maxSubarraySum is from arr1 and arrk.
    if summ > 0 and k > 2:
      return (self._kadane(arr, sz) + summ * (k - 2)) % kMod
    return self._kadane(arr, sz) % kMod

  def _kadane(self, arr: list[int], sz: int) -> int:
    ans = 0
    summ = 0
    for i in range(sz):
      a = arr[i % len(arr)]
      summ = max(a, summ + a)
      ans = max(ans, summ)
    return ans
 # code by PROGIEZ