#1191

K-Concatenation Maximum Sum

expert · 1155 · lc medium +32 · verified · 25.3% accepted · 1,503 likes · top 4%

Description

You are given an integer array arr and an integer k. Form a new array by concatenating arr exactly k times.

Return the maximum subarray sum within this concatenated array. An empty subarray has a sum of 0.

Since the answer can be very large, return it modulo 10⁹ + 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

Code

1

2

3

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: