Auto comment: topic has been updated by __Tanzeel__ (previous revision, new revision, compare).

Do you have the link to the problem?

I do have one approach and want to test it.

The approach: Since we can't make any three elements a[j] > a[i] < a[k]. We're left with 2 choices, make sorted array, or reverse-sorted array. in order to create the array we can just copy & paste the given array into another variable and from the start if it's not sorted we can just modify the value. To create an increasing sorted array you have to start from the end.

upd: I just noticed there is 1 more choice. and that is to make a mountain. To do this you can just simply create dp sort of thing from the beginning and from the end. and consider each element as the peak of the mountain. And this case contains the other 2 cases.

code: https://pastebin.com/d6bFy9YH Sorry for the bad English.

As far as I understood, the problem is to find an array that is initially increasing then decreasing. So we first need to fix the pivot element i.e the highest element in the middle. Let us brute force that pivot element as the ith element. Now you need to calculate the sum of the left part and the right part.

I will explain for the left part, as calculating the right part is exactly the same. Maintain a $$$dp$$$ array, $$$dp[i]$$$ is the sum of the construction of the increasing sequence adhering to the rules $$$arr[i]<=m[i]$$$.

To calculate $$$dp[i]$$$ , let $$$j$$$ be the previous smaller element than the $$$i^{th}$$$ element (can be calculated using stack in linear time). $$$dp[i]=dp[j]+(i-j)*m[i]$$$ as all the places greater than m[i] will be occupied by m[i] itself. similarly maintain another $$$dp2[]$$$ array for the reverse array for the right part and the asnwer is just $$$max(dp[i]+dp2[i+1])$$$ for all $$$i$$$.

Monotonic Stack for prefix and suffix

long long specialSum(vector<int> m, int n) {
        // write code here
        
        stack<long long int> s ;
        vector<long long int> pre(n) , suf(n);

        for(long long int i = 0 ; i < n ; i ++ ) 
        {
            
            while(s.size() && m[s.top()] >=  m[i]) 
                   s.pop() ;
            
            
            if(s.size() == 0)
                 pre[i] = m[i] * (i + 1);
            else
                 pre[i] = pre[s.top()] + m[i] * ( i - s.top()) ;
            
            s.push(i) ;
        }
        
        while(s.size()) 
            s.pop() ;
        
        for(long long int i = n - 1 ; i >= 0 ; i -- ) 
        {
            
            while(s.size() && m[s.top()] >=  m[i]) 
                      s.pop() ;
    
            if(s.size() == 0)
                 suf[i] = m[i] * ( n - i );
            else
                 suf[i] = suf[s.top()] + m[i] * (s.top() - i) ;
            
            s.push(i) ;
        }
        
        
        int long long ans = 0 ;
         
        for(int i = 0 ; i < n ; i ++ ) 
            ans = max(ans , pre[i] + suf[i] -  m[i]) ;
        
        return ans ;
    }

What are the constraints?