LeetCode: K-Concatenation Maximum Sum Posted on February 10, 2020July 26, 2020 by braindenny K-Concatenation Maximum Sum Similar Problems: CheatSheet: LeetCode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #kadane 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 10^9 + 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 <= 10^5 1 <= k <= 10^5 -10^4 <= arr[i] <= 10^4 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: ## https://code.dennyzhang.com/k-concatenation-maximum-sum ## Basic Ideas: Kadane ## ## If we include one repeition of the list, we can include all ## ## Complexity: Time O(n), Space O(1) class Solution: def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: n = len(arr) totalSum = sum(arr) res = 0 if totalSum >= 0: res = totalSum*(max(0, k-2)) nums = [0]*n if k > 1: nums = [0]*2*n for i in range(n): nums[i] = arr[i] nums[i+n] = arr[i] else: for i in range(n): nums[i] = arr[i] # Kadane maxSum = -sys.maxsize maxSoFar = 0 for i in range(len(nums)): v = nums[i] maxSoFar = max(v, maxSoFar+v) maxSum = max(maxSum, maxSoFar) res += maxSum return max(res, 0) % (10**9+7) Post Views: 0