Find maximum sum by replacing the Subarray in given range

By Ann Roberts On Jan 27, 2023

Given an array arr[], the task is to find the maximum sum possible such that any subarray of the indices from [l, r] i.e all subarray elements from arr[l] to arr[r] can be replaced with |arr[l] – arr[r]| any number of times.

Examples:

Input: arr[] = { 9, 1}
Output: 16
Explanation: The subarray [l, r] can choose as [0, 1] so it can be replaced as { | 9 – 1 |, | 9 – 1 | } = {8, 8} this is the only array that gives the maximum sum as 16.

Input: arr[] = {1, 1, 1}
Output: 3
Explanation: The array from indices [1, 2] can be chosen then the array becomes {1, |1 – 1|, |1 – 1| } which is equal to {1, 0, 0} now choosing the subarray from indices [0, 2] the array becomes { | 1 – 0 |, |1 – 0 |, | 1 – 0 |} which is equal to {1, 1, 1}. The maximum possible sum is 3.

Approach: To solve the problem follow the below idea:

This problem can be solved greedily by figuring out a way through observations for replacing the array with the maximum elements. The observation is like if any else chooses max one) having more than two elements to the left or right we can replace the array with that elements by doing the following operations:

Consider n = 4 and maximum element is arr[1] so {arr[0], arr[1], arr[2], arr[3]}

In the first operation choosing subarray [2, 3] the array becomes {arr[0 ], arr[1], |arr[2] – arr[3]|, |arr[2] – arr[3]|}

In the second operation choosing subarray [2, 3] the array becomes { arr[0], arr[1], 0, 0}

In the third operation choosing the subarray [1, 3] the array becomes { arr[0], arr[1], arr[1], arr[1]}

In the fourth operation on choosing the subarray [0, 1] the array becomes {| arr[0] – arr[1]|, |arr[0] – arr[1]|, arr[1], arr[1]}

In the 5th and 6th operations we choose subarrays [0, 1] and [0, 2] and the final array becomes {arr[1], arr[1], arr[1], arr[1]}.

In this way for n > 4 we can replace all the array elements with the max element of the array.

Edge cases for n = 3, n = 2:

For n = 2 we take max({2 * abs(arr[0] – arr[1]), arr[0] + arr[1]});

For n = 3 we take max({3 * (abs(arr[0] – arr[1])), 3 * (abs(arr[2] – arr[1])), 3 * arr[0], 3 * arr[2], arr[0] + arr[1] + arr[2]} because the middle element doesn’t have 2 elements on either of the sides for n = 3.

Follow these steps to solve the above problem:

Check if the size of the array is 2 only possible sums are 2 * abs(arr[0] – arr[1]), arr[0] + arr[1] return max of all.
Check if the size of the arrays is 3 all possible sums are 3 * (abs(arr[0] – arr[1])), 3 * (abs(arr[2] – arr[1])), 3 * arr[0], 3 * arr[2], arr[0] + arr[1] + arr[2] return a max of all.
If the size is >3 then we can replace all the elements with the maximum element
Initialize a variable mx = 0.
Iterate through the array and find the maximum element
Return n*mx.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int find_maxsum(int arr[], int n)

{

if (n == 2)

return max(

{ 2 * abs(arr[0] - arr[1]), arr[0] + arr[1] });

else if (n == 3)

return max({ 3 * (abs(arr[0] - arr[1])),

3 * (abs(arr[2] - arr[1])), 3 * arr[0],

3 * arr[2],

arr[0] + arr[1] + arr[2] });

int mx = 0;

for (int i = 0; i < n; i++)

mx = max(arr[i], mx);

return n * mx;

}

int main()

{

int arr[] = { 1, 9 };

int n = sizeof(arr) / sizeof(arr[0]);

int arr2[] = { 1, 1, 1 };

int m = sizeof(arr2) / sizeof(arr2[0]);

cout << find_maxsum(arr, n) << endl;

cout << find_maxsum(arr2, m) << endl;

}

Time Complexity: O(N) where N is the size of the array.
Auxiliary Space: O(1)