Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
1.1.
Example - 
1.2.
More Examples-
2.
Naive Approach
2.1.
C++ Code:
3.
Output:
3.1.
Time Complexity: O(N ^ 2)
3.2.
Space Complexity: O(N)
4.
Efficient Approach
5.
Implementation
5.1.
Output
5.2.
Time Complexity : O(NlogN)
5.3.
Space Complexity : O(N)
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

Maximize sum of array by reducing array elements to contain no triplets (i, j, k) where a[i] < a[j] and a[i] < a[k] and j <i < k

gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

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;
}
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Output:

Sum = 13
Final Array = 1 2 2 2 6 

Time Complexity: O(N ^ 2)

We are iterating over each element and making it the peak. Then, we are again iterating over the left and right subarray and updating the elements. Thus, we have used two nested loops that take O(N) time. Therefore the total time complexity of the solution is O(N ^ 2), where N is the length of the array.

Space Complexity: O(N)

We created two new arrays - ‘temp’ and ‘ans’ of length N to store the temporary and final array. Therefore, the space complexity of the above approach is O(N).

Efficient Approach

In our previous approach, we made every element as a peak element and then compared the sum of the resultant array to maximize the sum of the array. We can improve the complexity by finding the sum efficiently.

Consider a segment of the array from ‘l’ to ‘r’. Let ‘mi’ be the index of the minimum element in this segment. Now, there are two possibilities - the peak element of this segment lies in the range [‘l’, ‘mi’) or the peak element lies in the range (‘mi’, ‘r’]. In the first case, all the elements from [‘mi’, ‘r’] will have a value equal to ‘arr[mi]’, and in the second case, all the elements from [‘l’, ‘mi’] will have a value equal to ‘arr[mi]’.

We will utilize this observation to narrow down the range in which the peak element can exist. Let us define a recursive function ‘getPeak(l, r)’ that returns the required peak element of the given array. Initially ‘l’ = 0 and ‘r’ = ‘N’-1.

  1. Base Case: if ‘l’ == ‘r’, compare the current sum of the array with maximum sum to maximize the sum of the array and update the peak accordingly.
  2. Search the index of the smallest element, say ‘mi’.
  3. Make 2 recursive calls:
    1. Assume that the peak is in the left half ( [‘l’, ‘mi’) ). The sum of values given by the right half will equal ‘arr[mi]’*(‘r’ - ‘mi’ + 1). Make a recursive call to get the peak element from the left half.
    2. Assume the peak element is in the right half. The sum of values given by the left half will equal ‘arr[mi]’ * (‘mi’ - ‘l’ + 1). Make a recursive call to get the peak element from the right half.
  4. After finding the required peak, print the array and the sum.

In the above approach, the height of the recursive tree can go till O(N). However, in each level of the recursive tree, there will be O(N) elements, and at each level, the time taken will be O(N) to find the minimum element by iterating. So the total time complexity will still be O(N^2), where N is the array’s length.

To optimize the approach, we can use a segment tree to find the minimum element at each level such that query(‘l’, ‘r’) will return the index of the minimum element in the range [‘l’, ‘r’]. 

Implementation

#include <bits/stdc++.h>
using namespace std;

// Variable to store peak
int peak;

// Variable to store maximum sum
int maxi = -1;
 
// Array for creating segment tree
int tree[100001];
 
// Building segment tree
void built(int l, int r, int i, int a[])
{

    // Base Case
    if (l == r) {
        tree[i] = l;
        return;
    }
 
    // Finding mid element of the range
    int m = l + (r - l) / 2;
 
    // Recursive call over left half
    built(l, m, 2 * i, a);
 
    // Recursive call over right half
    built(m + 1, r, 2 * i + 1, a);
 
    if (a[tree[2 * i]] < a[tree[2 * i + 1]])
        tree[i] = tree[2*i];
    else
        tree[i] = tree[2*i + 1];
}
 
// Function to find index of the minimum element
int query(int l, int r, int s, int e, int index, int a[])
{

    // If the segment is invalid
    if (s > r || e < l) return -1;
 
    // If the segment is completely inside range
    if (s >= l && e <= r) return tree[index];
 
    // Finding the mid index
    int m = s + (e - s) / 2;
 
    // Recursive call over left half
    int d1 = query(l, r, s, m, 2 * index, a);
 
    // Recursive call over right half
    int d2 = query(l, r, m + 1, e, 2 * index + 1, a);
 
    // Returning the final answer
    if (d1 == -1) return d2;
    if (d2 == -1) return d1;
    if (a[d1] < a[d2]) return d1;
    else return d2;
}
 
// Function for finding the optimal peak
void optimalPeak(int l, int r, int val,
                int n, int a[])
{
    if (l > r) return;
 
    // Base Case
    if (l == r) {
 
        // Comparing to maximize the sum of the array
        if (val + a[l] > maxi) {
            maxi = a[l] + val;
            peak = l;
            return;
        }
        return;
    }
 
    // Index of minimum element in range [l,r]
    int mi = query(l, r, 0, n - 1, 1, a);
 
    int val1 = a[mi] * (mi - l + 1);
 
    // Recursive call over left half
    optimalPeak(mi + 1, r, val + val1, n, a);
 
    // Update the max and peak val
    if (mi + 1 > r) {
        if (val + val1 > maxi) {
            maxi = val + val1;
            peak = mi;
        }
    }
 
    int val2 = a[mi] * (r - mi + 1);
 
    // Recursive call over left half
    optimalPeak(l, mi - 1,
                val + val2, n, a);
 
    // Update the max and peak val
    if (l > mi - 1) {
        if (val + val2 > maxi) {
            maxi = val + val2;
            peak = l;
        }
    }
}

void solve(int n, int arr[])
{
    // Initializing segment tree
    built(0, n - 1, 1, arr);
 
    // Finding the required peak
    optimalPeak(0, n - 1, 0, n, arr);
 
    int ans[n];
    ans[peak] = arr[peak];
 
    // Finding the answer array according to peak
    for (int i = peak + 1; i < n; i++) {
        ans[i] = min(ans[i - 1], arr[i]);
    }
 
    for (int i = peak - 1; i >= 0; i--) {
        ans[i] = min(arr[i], ans[i + 1]);
    }
 
    // Calculating sum of answer array
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += ans[i];
    }
 
    // Printing the answer
    cout << "Sum = " << sum << endl;
 
    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;
}

Output

Sum = 13
Final Array = 1 2 2 2 6 

Time Complexity : O(NlogN)

In the worst case, the depth of the recursive tree can go till O(N). At each level of the recursive tree, there can be O(N) elements, and the time taken at each level will be O(logN) because of the query on the segment tree.

The recurrence relation in the worst case will look like this:

T(N) = T(N-1) + T(1) + O(logN)

The solution of the above recurrence relation is T(N) = O(NlogN).

Therefore, the total time complexity of the above approach is O(NlogN).

Space Complexity : O(N)

We have created a segment tree for the given array, which will take O(N) space. 

Also, the Recursion depth can be O(N) in the worst case.

Therefore, the total space complexity of the above approach is O(N).

FAQs

  1. What is a Segment Tree data structure?
    A Segment Tree also called a statistic tree, is a tree data structure that allows us to answer range queries over an array efficiently and at the same time, is flexible to allow modification of the array. We can perform various operations such as finding the sum of consecutive array elements, finding the minimum of some segment of the array, etc.
     
  2. What is Recursion?
    Recursion is the process in which a function calls itself directly or indirectly. Recursion can be used to solve a larger problem by dividing it into smaller problems, solving those smaller problems effectively, and then combining the results to get the answer for the larger problem.

Key Takeaways

In this article, we discussed how to maximize the sum of the array by reducing its elements by 1 such that it contains no triplets (i,j,k) where a[i] < a[j] and a[i] < a[k] and j < i < k. We also discussed the time and space complexity of our solution. If you want to solve more such problems such as sum of two arraysmerge K sorted arrays, etcyou can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, all the best for your future endeavors, and Keep Coding.

Previous article
Queries to calculate sum with alternating signs of array elements in a given range
Next article
Query to find the length of the longest subarray consisting of only 1s
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass