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.

Maximum Subarray Sum of an Array Repeated k Times

Hints

1. The repeated array can have up to 10^10 elements, so think about the answer without building it.
2. Solve the k = 1 case first, then ask which shapes a subarray can take once it is allowed to cross the boundary between copies.
3. Consider what a subarray that covers one or more whole copies gains or loses for each copy it covers.

Approach

Let total be the sum of one copy of nums. Every non-empty subarray of the repeated array either lies inside a single copy, or starts in copy i and ends in a later copy j. A subarray of the first kind sums to at most best_in, the maximum non-empty subarray sum of nums, which Kadane's scan finds in one pass (cur is the best sum of a non-empty run ending at the current element: max(x, cur + x)). A subarray of the second kind is a non-empty suffix of copy i, then the j - i - 1 whole copies between, then a non-empty prefix of copy j, so its best sum is best_suffix + m * total + best_prefix for some m between 0 and k - 2. That expression is largest at m = k - 2 when total > 0 and at m = 0 otherwise. For k = 1 there is no boundary to cross and the answer is best_in. For k >= 2 the answer is max(best_in, best_suffix + middle + best_prefix), where middle = (k - 2) * total if total > 0, else 0. Because every candidate run, prefix and suffix is non-empty, an all-negative array returns its largest element rather than 0. The repeated array (up to 10^10 elements) is never built. Magnitudes: per-copy sums are at most 10^9 and (k - 2) * total is at most about 10^14, so 64-bit integers suffice (Java long, C++ long long), and JavaScript numbers stay exact below 2^53. Edge cases: one element, k = 1, k = 2 (no whole middle copy), all negative, all zero, and a copy total of exactly 0, where the crossing run can tie the in-copy maximum.

• Time complexity: O(n)
• Space complexity: O(1)