Watch 7 video solutions for Maximum Total Subarray Value I, a medium level problem involving Array, Greedy. This walkthrough by Sanyam IIT Guwahati has 352 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums of length n and an integer k.
You need to choose exactly k non-empty subarrays nums[l..r] of nums. Subarrays may overlap, and the exact same subarray (same l and r) can be chosen more than once.
The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).
The total value is the sum of the values of all chosen subarrays.
Return the maximum possible total value you can achieve.
Example 1:
Input: nums = [1,3,2], k = 2
Output: 4
Explanation:
One optimal approach is:
nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 1 = 2.Adding these gives 2 + 2 = 4.
Example 2:
Input: nums = [4,2,5,1], k = 3
Output: 12
Explanation:
One optimal approach is:
nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.Adding these gives 4 + 4 + 4 = 12.
Constraints:
1 <= n == nums.length <= 5 * 1040 <= nums[i] <= 1091 <= k <= 105Problem Overview: You are given an integer array and need to split it into one or more subarrays so the total "value" across chosen subarrays is maximized. The key observation is that extending a subarray is only beneficial when the next element increases the value contribution. This leads to a greedy scan across the array.
Approach 1: Simple Observation (Greedy) (Time: O(n), Space: O(1))
The optimal strategy comes from noticing that only positive increases between consecutive elements add useful value. When nums[i] > nums[i-1], extending the current segment increases the subarray’s contribution. When the sequence drops or stays flat, continuing the segment provides no additional gain, so it is safe to effectively start a new subarray.
Implementation is straightforward: iterate once through the array and accumulate every positive difference nums[i] - nums[i-1]. Each positive jump represents value that can be captured by forming or extending a profitable subarray. Negative or zero differences are ignored because they do not increase the total value.
This greedy reasoning works because the contribution of each increasing step is independent. Whether you treat the increase as part of one long subarray or several smaller ones, the total accumulated gain remains the same. Summing all positive differences therefore gives the maximum possible total value.
The algorithm performs a single pass over the array and maintains only a running total, resulting in O(n) time and O(1) extra space. The technique relies on identifying local profitable transitions, a common pattern in greedy algorithms and sequential processing of arrays.
Recommended for interviews: Interviewers expect the greedy observation. A brute force approach that enumerates all possible subarrays quickly becomes quadratic and unnecessary. Recognizing that only positive adjacent differences contribute demonstrates strong problem‑solving intuition and familiarity with greedy patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^2) | O(1) | Useful for understanding the problem by checking every subarray, but too slow for large inputs. |
| Greedy Positive Difference Accumulation | O(n) | O(1) | Best approach for the general case. Single pass over the array captures all profitable increases. |