Problem
In this problem, you are given an array ‘arr’ of length ‘N’. You can perform the following operation on the array:
- Choose any valid index ‘i’ and decrease the element at that index by 1.
You can perform the above operation any number of times so that after performing all the operations, the array contains no triplet (‘i’, ‘j’, ‘k’) where ‘arr[i]’ < ‘arr[j]’ and ‘arr[i]’ < ‘arr[k]’ and ‘j’ < ‘i’ < ‘k’. The goal is to maximize the sum of the array satisfying the above condition. Print the final array.
Example -
Input: N = 5, arr = [1, 4, 3, 2, 6]
Output: 1 2 2 2 6
Explanation:
The original array does not satisfy the condition given in the problem statement. Consider the triplet (2,1,4), ‘arr[2]’ = 3, ‘arr[1]’ = 4 and ‘arr[4]’ = 6. Here, ‘arr[i]’ < ‘arr[j]’ and ‘arr[i] < ‘arr[k]’. Similarly, the triplets (3,1, 4), (3, 2, 4) violate the condition. Therefore we have to perform the operation some number of times until we get an array that doesnot violates the given condition.
We can form many arrays that will not violate the condition given in the problem statement.
For eg:
[1, 2, 3, 2, 1] can be from the original array and it contains no triplet (i,j,k) where ‘arr[i]’ < ‘arr[j]’ and ‘arr[i]’ < ‘arr[k]’ and ‘j’ < ‘i’ < ‘k’.
Similarly, [1, 4, 3, 2, 2], [1, 2, 3, 2, 2], [1, 2, 2, 2, 6], [1, 2, 2, 2, 6], etc are all valid arrays as the donot contain any triplet that violates the condition. Among all such arrays, our goal is to maximize the sum of the array. The array with maximum sum is [1, 2, 2, 2, 6], having sum of elements equal to 13. Therefore, the answer is [1, 2, 2, 2, 6].
More Examples-
Input: N = 4, arr = [3, 2, 5, 1].
Output: 2 2 5 1
Explanation:
We can create several valid arrays, eg: [1, 2, 4, 1], [2, 2, 5, 1], [3, 2, 2, 1], etc. In all there arrays, there is not triplet (i, j, k) where ‘arr[i]’ < ‘arr[j]’ and ‘arr[i]’ < ‘arr[k]’ and ‘j’ < ‘i’ < ‘k’. Among all these arrays, we have to print the array having maximum sum. Therefore the answer is [2, 2, 5, 1], having sum = 10.
Input: N = 6, arr = [4, 3, 7, 6, 1, 8].
Output: 3 3 7 6 1 1
Also read, Euclid GCD Algorithm
Naive Approach
According to the problem statement, there should be no index ‘i’ smaller than any element on its left and smaller than any element on its right. Maintaining this property, we have to maximize the sum of the array.
If we think of the final form of the array, it would first be increasing and then after a point, it will be decreasing, i.e., ‘arr[0]’ <= ‘arr[1]’ <= … <= ‘arr[i]’ >= ‘arr[i+1]’ … >= ‘arr[N]’ for some ‘i’. Let us call this ‘i’ as the peak element. Only such an array will satisfy the above condition.
Now we can simply brute-force over every element, set it as the array’s peak, and update the remaining elements accordingly. We will store the array having a maximum sum for every such peak element to maximize the sum of the array.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
/*
Function to maximize the sum of the array
maintaining the given property
*/
void solve(int n, int a[])
{
int cnt = 0;
/*
temp will store the temporary array
when ith index is the peak
*/
int temp[n];
// ans will store the final array.
int ans[n];
// Check the array for each index
for (int i = 0; i < n; i++) {
// Set a[i] as the peak
temp[i] = a[i];
// Cur will store the sum of current array
int cur = temp[i];
// Update left part
for (int j = i - 1; j >= 0; j--) {
temp[j] = min(temp[j + 1], a[j]);
cur += temp[j];
}
// Update right part
for (int j = i + 1; j < n; j++) {
temp[j] = min(temp[j - 1], a[j]);
cur += temp[j];
}
/*
Checking if current sum > cnt
to maximize the sum of the array
*/
if (cnt < cur) {
cnt = cur;
// Updating final array
for (int j = 0; j < n; j++) {
ans[j] = temp[j];
}
}
}
// Finding sum
int sum = 0;
for (int i = 0; i < n; i++) {
sum += ans[i];
}
cout << "Sum = " << sum << endl;
// Printing final array
cout << "Final Array = ";
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
cout<<endl;
}
// Drive Code
int main()
{
int a[] = {1, 4, 3, 2, 6};
int n = 5;
solve(n,a);
return 0;
}
46+ registered 