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