Skip to content

1191. K-Concatenation Maximum Sum 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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>& A, int sz) {
    int ans = 0;
    int sum = 0;
    for (int i = 0; i < sz; ++i) {
      const int a = A[i % A.size()];
      sum = max(a, sum + a);
      ans = max(ans, sum);
    }
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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[] A, int sz) {
    int ans = 0;
    int sum = 0;
    for (int i = 0; i < sz; ++i) {
      final int a = A[i % A.length];
      sum = Math.max(a, sum + a);
      ans = Math.max(ans, sum);
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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, A: list[int], sz: int) -> int:
    ans = 0
    summ = 0
    for i in range(sz):
      a = A[i % len(A)]
      summ = max(a, summ + a)
      ans = max(ans, summ)
    return ans