Maximum Total Subarray Range with Repeatable Choices
Company: TCS
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given an integer array `nums` and a positive integer `k`, select exactly `k` nonempty contiguous subarrays.
Selections may overlap. **The same endpoint pair may be selected more than once**, and each selection contributes separately to the total.
The value of one selected subarray is its largest element minus its smallest element. Return the greatest possible sum of the values of the `k` selections.
```cpp
class Solution {
public:
long long maxTotalValue(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums = [6,2,5], k = 4
Output: 16
Explanation: Selecting the whole array four times is allowed. Each selection has largest value 6 and smallest value 2, contributing 4, for a total of 16. No individual subarray can contribute more than 4.
```
**Example 2:**
```text
Input: nums = [9], k = 7
Output: 0
Explanation: Select the single-element subarray seven times. Every selected value is 9-9 = 0. Repeated selection makes this input valid even though only one distinct subarray exists.
```
### Constraints
- `1 <= nums.length <= 50000`.
- `0 <= nums[i] <= 1000000000`.
- `1 <= k <= 100000`.
### Clarifying Questions
- Must the selected subarrays be different? No. Reusing identical endpoints is explicitly allowed.
- Must the selections be disjoint? No; overlap is allowed.
- Does a one-element subarray have value zero? Yes.
- Are the selected endpoints required as output? No, return only the maximum total.
### What a Strong Answer Covers
- Exactly `k` nonempty selections, including repeated endpoint pairs and overlap.
- The maximum-minus-minimum value definition for each selection.
- A proof that its total cannot be improved.
- Single-element and all-equal arrays, large `k`, numeric bounds, and resource complexity.
### Follow-up Questions
- How would the feasible selections change if identical endpoint pairs could not be reused?
- What extra output would be needed if the selected subarrays also had to be returned?
```hint Separate a bound from a construction
Compare any subarray's largest and smallest elements with the largest and smallest elements of the entire input. Then use the permission to repeat a selection.
```
Overview: Maximize the total maximum-minus-minimum value of k subarray selections when identical endpoints may repeat. Includes examples, proof, and a C++ solution.