Beautiful Subarray Pair

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote

Problem statement

A subarray is a contiguous part of an array.

Your task is to find the maximum possible beauty of non-overlapping non-empty subarray pairs present in the array ‘A’.

Beauty of a subarray pair is defined as the absolute difference of the sum of elements of both the subarrays.

A subarray pair is said to be non-overlapping if there is no index common to both subarrays.

Example: 
Input: [1,2,-3,4,5]

Output: 12

In the given array we can consider the subarray pair { [-3] , [4,5] } which has the maximum beauty.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the size of array ‘A’.

The second line of each test case contains ‘N’ single space-separated integers, elements of the array ‘A’.
Output format : 
For each test case, Return the maximum possible beauty of all valid subarray pairs.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10000
-10^9 <= A[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
5   
-6 3 1 -5 9
4
-3 1 9 -10
Sample Output 1 :
16
20
Explanation Of Sample Input 1 :
For the first case:
We can consider the subarray pair { [-6,3,1,-5] , [9] } which has the maximum beauty (9-(-6+3+1-5) = 16).

For the second case:
We can consider the subarray pair { [1,9] , [-10] } which has the maximum beauty ((1+9)-(-10) = 20).
Sample Input 2 :
2
8
6 1 -50 1 50 30 6 -100
6
55 19 -21 13 -10 -67
Sample Output 2 :
187
159
Hint

Check all possible subarray pairs.

Approaches (2)
Brute Force

In this approach, we will check all possible pairs of subarrays for finding maximum beauty. We can take four nested for loops. First, two loops will fix the first subarray and the last two will fix the other. In this way, we can find the beauty of all possible pairs and return the maximum beauty.


 

The steps are as follows:-

function getMaxBeauty(int N, [int]A):

  1. Initialize the variable ‘maxBeauty’ with 0, it denotes the maximum possible beauty of a subarray pair.
  2. Run a for loop from i=0 to N-2 for fixing the starting point of the first subarray and initialize a variable ‘sum1’ that will denote the sum of elements of the first subarray.
    • Run another for loop from j=i to N-2 for fixing the endpoint of the first subarray and add the values of elements to sum1.
      • Run another for loop from k=j+1 to N-1 for fixing the start point of the second subarray and initialize a variable ‘sum2’ denoting the sum of elements of the second subarray.
        • Run another for loop from l=k to N-1 for fixing the endpoint of the second subarray and add the values of elements to sum2.
          • Update the value of maxBeauty.
  3. Return the value of maxBeauty at the end.
Time Complexity

O( N⁴ ), Where ‘N’ is the size of the given array ‘A’.

 

We are using four nested for loops for traversing over all possible subarray pairs.

Hence the time complexity is O( N⁴ ).

Space Complexity

O( 1 ).

 

We are using constant extra space for string sums and the maximum beauty of subarray pairs.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Beautiful Subarray Pair
Full screen
Console