Reverse Subarray To Maximize Array Value

Hard
0/120
Average time to solve is 45m
7 upvotes
Asked in companies
AppleUnthinkable Solutions

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5
5 4 1 7 2
Sample Output 1:
17
Explanation for sample input 1:
The current beauty of the array is |5 - 4| + |4 - 1| + |1 - 7| + |7 - 2| = 15, after reversing the subarray [4, 1, 7, 2] beauty becomes = |5 - 2| + |2 - 7| + |7 - 1| + |1 - 4| = 17, which is the maximum beauty we can obtain.
Sample Input 2:
2
4
4 3 7 1
5
4 5 3 7 6
Sample Output 2:
13
10
Explanation for sample input 2:
For test case 1, the initial beauty value is 1 + 4 + 6 = 11, on reversing the subarray [3, 7, 1] the beauty becomes 3 + 6 + 4 = 13.

For test case 2, reverse the subarray [5, 3, 7] to get a beauty value of 10.
Hint

Think of a brute force approach. Check the answer for every subarray.

Approaches (3)
Brute Force Approach:
  • 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.
Time Complexity

O(N ^ 3), where N is the size of the array ‘NUMS’.

 

There are a total of N*(N-1) = N ^ 2 combinations of left and right and we also need to find the beauty of the whole array of size N for each combination thus the net time complexity is O(N ^ 3).

Space Complexity

O(N), where N is the size of the array ‘NUMS’.

 

As we are using an extra array of size ‘N’, thus raising the space complexity to O(N).

Code Solution
(100% EXP penalty)
Reverse Subarray To Maximize Array Value
Full screen
Console