Maximum Subarray Sum of an Array Repeated K Times

Given an integer array nums and a positive integer k, form the repeated array by writing nums out k times back to back. For nums = [1, 2] and k = 3, the repeated array is [1, 2, 1, 2, 1, 2]. Return the largest sum of a non-empty contiguous subarray of the repeated array.

The task comes in two steps: first solve it for the array itself (k = 1), then for any k.

Function Signature

def max_repeated_subarray_sum(nums: list[int], k: int) -> int:

Rules

• A subarray is a contiguous, non-empty run of elements of the repeated array. It may cross the boundary between copies and may cover several whole copies.
• Because the subarray is non-empty, the answer is negative when every element is negative.
• Return the exact sum, with no modulo.

Constraints

• 1 <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= 10^5
• The repeated array can have up to 10^10 elements.
• The answer's absolute value is at most 10^14. That exceeds 2^31 - 1 but stays within 2^53, so use 64-bit or arbitrary-precision integers.

Examples

Example 1

Input: nums = [2, -5, 3], k = 3
Output: 5

The repeated array is [2, -5, 3, 2, -5, 3, 2, -5, 3]. The subarray [3, 2], which crosses a boundary between copies, sums to 5. With k = 1 the answer would be 3.

Example 2

Input: nums = [1, -3, 4], k = 3
Output: 8

The repeated array is [1, -3, 4, 1, -3, 4, 1, -3, 4]. The subarray from the first 4 to the end, [4, 1, -3, 4, 1, -3, 4], sums to 8.

Example 3

Input: nums = [-4, -2, -7], k = 5
Output: -2

Every element is negative, so the best non-empty subarray is the single element -2.