Beautiful Subarray Pair

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.

In this approach, we’ll precompute the maximum and minimum subarray sums in a 2D array. Take two 2D arrays, one for storing the minimum and maximum subarray sums in the prefix fashion and the other in suffix fashion. 

We will be using kadane’s algorithm to get the maximum and minimum subarray sums. After storing the minimum and maximum sums iterate through the indexes of the array and check for the maximum beauty pair. 

The possible maximum beauties at any index can be the difference between the maximum subarray sum of prefix part and minimum subarray sum of suffix part or the difference between the minimum subarray sum of prefix part and maximum subarray sum of suffix part.

Prefix[i][0]- It stores the maximum subarray sum from index 0 tol index i.

Prefix[i][1]- It stores the minimum subarray sum from index 0 to index i.

Suffix[i][0]- It stores the maximum subarray sum from index i to index N-1.

Suffix[i][1]- It stores the minimum subarray sum from index i to index N-1.

The steps are as follows:-

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

1. Declare two 2D arrays ‘prefix’ and ‘suffix’ to store the minimum and maximum subarray sums in prefix and suffix order respectively.
2. Initialize the variables ‘maxSum’ with -1e9, ‘minSum’ with 1e9 denoting the minimum and maximum sum up to the current index respectively.
3. Initialize the variable ‘maxCurr’ with zero and ‘minCurr’ with zero denoting the current maximum and minimum sum respectively.
4. Run a for loop form i=0 to N-1
   • Add the current element int maxCurr and minCurr.
   • Update the values of maxSum and minSum.
   • Assign the values maximum and minimum subarray sums to prefix[i].
   • If the maxCurr is less than zero change it to zero.
   • If the minCurr is greater than zero change it to zero.
5. Now traverse the array in reverse order and repeat the above operations to assign values in ‘suffix’.
6. Initialize the variable ‘maxBeauty’ with -1e9 denoting the maximum beauty of subarray pairs.
7. Run a for loop from i=0 to N-2
   • Update the value of maxBeauty with max value of ( prefix[i][0]-suffix[i+1][1]) and (suffix[i+1][0]-prefix[i][1]).
8. Return the value of maxBeauty.