You are given an integer array nums. The value of this array is defined as the sum of |nums[i] - nums[i + 1]| for all 0 <= i < nums.length - 1.
You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.
Find maximum possible value of the final array.
Example 1:
Input: nums = [2,3,1,5,4] Output: 10 Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.
Example 2:
Input: nums = [2,4,9,24,2,1,10] Output: 68
Constraints:
2 <= nums.length <= 3 * 104-105 <= nums[i] <= 105In this problem, the array value is defined as the sum of |nums[i] - nums[i-1]| for all adjacent elements. The goal is to choose exactly one subarray to reverse so that this total value becomes as large as possible. A brute force strategy that tries every possible subarray reversal would take O(n^2) or worse, which is inefficient for large inputs.
A better approach begins by computing the base value of the array without any reversal. Then, analyze how reversing a segment changes only the boundary pairs around that segment. By evaluating potential gains when reversing prefixes, suffixes, and internal segments, you can track the maximum improvement using a greedy observation. Carefully comparing adjacent differences and maintaining candidate extremes allows the algorithm to compute the best possible gain in a single pass.
This optimized strategy runs in O(n) time with O(1) extra space, making it suitable for large arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (try all subarray reversals) | O(n^2) | O(1) |
| Greedy with boundary gain analysis | O(n) | O(1) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
What's the score after reversing a sub-array [L, R] ?
It's the score without reversing it + abs(a[R] - a[L-1]) + abs(a[L] - a[R+1]) - abs(a[L] - a[L-1]) - abs(a[R] - a[R+1])
How to maximize that formula given that abs(x - y) = max(x - y, y - x) ?
This can be written as max(max(a[R] - a[L - 1], a[L - 1] - a[R]) + max(a[R + 1] - a[L], a[L] - a[R + 1]) - value(L) - value(R + 1)) over all L < R where value(i) = abs(a[i] - a[i-1])
This can be divided into 4 cases.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The greedy idea works because reversing a subarray only affects the boundary pairs around that segment. By focusing on the potential gain from those boundaries instead of recomputing the entire array value, the algorithm efficiently finds the best reversal.
Yes, this type of greedy array optimization problem is common in technical interviews. It tests your ability to analyze how local transformations affect a global metric and optimize beyond brute force solutions.
No complex data structure is required for this problem. The solution mainly relies on array traversal and mathematical observations about adjacent differences. Simple variables are used to track the current base value and the best possible improvement.
The optimal approach uses a greedy strategy. First compute the base sum of absolute differences, then analyze how reversing certain segments changes boundary contributions. By tracking the maximum possible gain from prefixes, suffixes, and internal segments, the result can be computed in linear time.