Maximum Subarray Sum of an Array Repeated K Times
Company: Microsoft
Role: Applied Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
Input: nums = [-4, -2, -7], k = 5
Output: -2
```
Every element is negative, so the best non-empty subarray is the single element `-2`.
Overview: A coding question that first asks for the largest sum of a non-empty contiguous subarray, then for the same quantity when the array is written out k times back to back. It tests subarray reasoning across copy boundaries, all-negative inputs, and sums that overflow 32-bit integers.
Read the full Microsoft Applied Scientist interview experience this question came from
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`. Implement `max_repeated_subarray_sum(nums, k)` so that it handles every `k` in the range below.
### 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. The answer can exceed `2^31 - 1`, so Java returns `long` and C++ returns `long long`.
### 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.
### Example 1
```text
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
```text
Input: nums = [-4, -2, -7], k = 5
Output: -2
```
Every element is negative, so the best non-empty subarray is the single element `-2`.
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 (Java long, C++ long long).
Examples
Input: ([2, -5, 3], 3)
Expected Output: 5
Explanation: Source Example 1: the run [3, 2] crosses a copy boundary and sums to 5; the best run inside one copy is only 3.
Input: ([2, -5, 3], 1)
Expected Output: 3
Explanation: k = 1 (step one): there is no copy boundary, so wrapping around to [3, 2] is not allowed; the answer is [3] = 3.
Hints
- The repeated array can have up to 10^10 elements, so think about the answer without building it.
- Solve the k = 1 case first, then ask which shapes a subarray can take once it is allowed to cross the boundary between copies.
- Consider what a subarray that covers one or more whole copies gains or loses for each copy it covers.