Last Updated: 17 Apr, 2021
Reverse Subarray To Maximize Array Value
Hard
Asked in companies
You are given an array of integers ‘NUMS’. The beauty of this array can be defined as:
The sum of absolute difference of each two consecutive elements.
In one operation you can reverse one subarray of ‘NUMS’. Your task is to find maximum beauty by performing the operation exactly once.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first line of each test case contains a single positive integer ‘N’ denoting the size of the ‘NUMS’ array.
The second line of each test case contains ‘N’ space-separated positive integers denoting the array elements.
Output Format:
For each test case, print a single line containing a single integer denoting the maximum beauty of the array ‘NUMS’ by doing the operation described above exactly once.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= NUMS[i] <= 10^8
Where ‘N’ is the size of the array ‘NUMS’ and ‘NUMS[i]’ is the ith element of the array.
Time Limit: 1 sec
Approaches
- There are a total of N*(N - 1) subarrays in the array.
- We need to choose every subarray, reverse it and check for the answer.
- Keep a variable left which goes from 0 to N-1 and keep a variable right which goes from left to N-1. left and right denote the starting and ending of the subarray we are going to reverse.
- As we need to keep the original array so copy the elements from the original array to a new temp array with one modification, copy the elements from [left, right] in reverse order.
- Calculate the beauty of this temp array.
- Continue this process for all left and right.
- Return the answer.
- In the previous approach after fixing left and right we had to calculate the beauty from the 1st index to the last, every time.
- Let our array look something like 0, 1 ...left-1, [left…..right], right+1…x, y where left, right, x, y are array indices.
- With little observation we can see that the beauty of the subarray from [0, left-1] will remain unchanged after reversing [left, right], similarly, the beauty contribution of the subarray from [right+1 to y] remains unchanged and [left+1, right-1] remains unchanged too.
- What changes is that we get new contributions from [left-1, right] and [left, right+1].
- In this algorithm first, first find out the original beauty of the initial array in the beginning. Let the initial beauty of the array be original_beauty.
- After reversal of the subarray [left, right] the new beauty value is a sum of:
- +|NUMS[left-1] - NUMS[right]| from the left conjunction.
- - |NUMS[left-1] - NUMS[left]| because NUMS[left] and NUMS[left+1] are not adjacent now.
- +NUMS[left] - NUMS[right+1] from the right conjunction.
- - |NUMS[right+1] - NUMS[right]| because NUMS[right] and NUMS[right+1] are not adjacent now.
- original_beauty from the original array.
- Check for the max ans amongst all left and right.
- Suppose our array is m, n ... a, [b ... c], d …. y, z. Where m is the array element at the 0th index and so on.
- We will consider reversing the subarray from b to c and see in which cases we get a better answer.
- Note that the value of |arr[i] - arr[i+1]| for(0 <= i < N - 1) does not change for any pair after reversion except possibly for those pairs containing a, b, c, and d.
- We only have 2 cases, when min(a, b), max(a, b) intersects with min(c, d), max(c, d), and when it does not. When it does intersect we have further 2 cases when min(a, b), max(a, b) completely overlaps min(c, d), max(c, d), and otherwise.
- CASE 1: When min(a, b), max(a, b) partially intersects min(c, d), max(c, d)
- Note that which amongst a, b is min(a, b) and which is max(a, b) does not affect the answer. The same goes for min(c, d), max(c, d).
- If plotting on a paper the figure looks something like:
- Let the initial beauty of the array be original_beauty.
- After reversal of the subarray if both the min values are on the same side, then the new beauty value is a sum of:
- +|min(a, b) - min(c, d)| from the left conjunction.
- - |max(a, b) - min(a, b)| because a and b are not adjacent now
- +|max(a, b) - max(c, d)| from the right conjunction..
- - |max(c, d) - min(c, d)| because c and d are not adjacent now.
- original_beauty from the original array.
- Otherwise the contributions are :
- +|min(a, b) - max(c, d)| from the left conjunction.
- - |max(a, b) - min(a, b)| because a and b are not adjacent now.
- +|max(a, b) - min(c, d)| from the right conjunction.
- - |max(c, d) - min(c, d)| because c and d are not adjacent now.
- original_beauty from the original array.
- In both cases, the new beauty value is not greater than the original beauty value we had. In this case, therefore we will not reverse the subarray.
- CASE 2: When min(a, b), max(a, b) completely overlaps min(c, d), max(c, d)
- If plotting on a paper the figure looks something like this:
- After reversal of the subarray if both the min values are on the same side, then the new beauty value is a sum of:
- +|min(a, b) - min(c, d)| from the left conjunction.
- - |max(a, b) - min(a, b)| because a and b are not adjacent now
- +|max(a, b) - max(c, d)| from the right conjunction..
- - |max(c, d) - min(c, d)| because c and d are not adjacent now.
- original_beauty from the original array.
- Otherwise the contributions are :
- +|min(a, b) - max(c, d)| from the left conjunction.
- - |max(a, b) - min(a, b)| because a and b are not adjacent now.
- +|max(a, b) - min(c, d)| from the right conjunction.
- - |max(c, d) - min(c, d)| because c and d are not adjacent now.
- original_beauty from the original array.
- In both cases again, the new beauty value is either less or exactly equal to the original beauty value we had. In this case, also, we will not reverse the subarray.
- CASE 3: When min(a, b), max(a, b) does not intersect with min(c, d), max(c, d)
- The values of a,b and c,d do not intersect this time.
- If plotting on a graph the graph looks something like:
- Let the initial beauty of the array be original_beauty.
- After reversal of the subarray if both the min values are on the same side, then the new beauty value is a sum of:
- +|min(a, b) - min(c, d)| from the left conjunction.
- - |max(a, b) - min(a, b)| because a and b are not adjacent now
- +|max(a, b) - max(c, d)| from the right conjunction..
- - |max(c, d) - min(c, d)| because c and d are not adjacent now.
- original_beauty from the original array.
- Otherwise the contributions are :
- +|min(a, b) - max(c, d)| from the left conjunction.
- - |max(a, b) - min(a, b)| because a and b are not adjacent now.
- +|max(a, b) - min(c, d)| from the right conjunction.
- - |max(c, d) - min(c, d)| because c and d are not adjacent now.
- original_beauty from the original array.
- In both cases, the new beauty value is greater than the original beauty value by 2 *( min(c, d) - max(a, b)). We reverse the subarray only when a,b do not intersect with c, d.
- As we found out, the increment in the answer we get by following Case 3 will be 2*(min(c, d) - max(a, b)). Thus
- Just traverse the array in a single iteration
- Find the maximum value of min(x, y) for any 2 adjacent array elements x, y, let it be MAX.
- Find the minimum value of max(x, y) for any 2 adjacent array elements x, y, let it be MIN.
- Add 2*(MAX - MIN) to the original beauty.
- At the end check for prefix and suffix reversal i.e when we reverse the array from the 0th index to some c or from some b to the (n-1)th index.
Similar problems