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:
1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5
Solution: Greedy
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int maxValueAfterReverse(vector<int>& nums) { const int n = nums.size(); int sum = 0; int gain = 0; int hi = INT_MIN; int lo = INT_MAX; for (int i = 0; i < n - 1; ++i) { int n1 = nums[i]; int n2 = nums[i + 1]; sum += abs(n1 - n2); gain = max({gain, abs(nums[0] - n2) - abs(n1 - n2), abs(nums[n - 1] - n1) - abs(n1 - n2)}); hi = max(hi, min(n1, n2)); lo = min(lo, max(n1, n2)); } return sum + max(gain, (hi - lo) * 2); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment