[Solved] Maximise Sum C++, Java , Python

You are given an array A consisting of N positive integers.

You are allowed to do the following operation any number of times:

• Select two integers l and r such that 1≤≤l<r≤N;
• Change Ai​ to min⁡(Al​,Ar​) for all l<i<r.

Find the maximum value of ∑i=1N​Ai​ that you can achieve after any (possibly zero) number of operations.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains a single integer N — the length of the array A.
  • The second line of each test case contains �N space-separated integers �1,2,…,A1​,A2​,…,AN​ representing the array A.

Output Format

For each test case, output on a new line, the maximum sum that you can achieve after any (possibly zero) number of operations.

Constraints

• 1≤1051≤T≤105
• 1≤1051≤N≤105
• 1≤1091≤Ai​≤109
• The sum of N over all test cases won’t exceed 5⋅1055⋅105.

Sample 1:

Input 3 2 2 3 3 5 1 7 4 5 5 5 5

Output 3 5 17 20

Explanation:

Test case 11: The only possible value of (l,r) can be (1,2)(1,2) but that does not impact any Ai​. Thus, the maximum sum we can achieve is 2+3=52+3=5.

Test case 22: Select (l,r) as (1,3)(1,3) and change 2=min⁡(1,3)=5A2​=min(A1​,A3​)=5. Thus, the array becomes [5,5,7][5,5,7] with sum 5+5+7=175+5+7=17.

Test case 33: Since all elements of the array are same, we cannot change any Ai​ using an operation. Thus, the maximum sum we can achieve is 5+5+5+5=205+5+5+5=20.

Solution

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

int main()
{
    // Read the number of test cases.
    long long t;
    cin >> t;
    
    // Loop through each test case.
    while (t--)
    {
        long long n;
        cin >> n;
        vector<long long> v(n);
        vector<pair<long long, long long>> vp;
        
        // Read the array elements and store them along with their indices in vp.
        for (long long i = 0; i < n; i++)
        {
            cin >> v[i];
            vp.push_back({v[i], i});
        }
        
        // Sort vp in descending order, based on the values of the elements.
        sort(vp.rbegin(), vp.rend());

        long long maxi = v[0]; // Initialize maxi with the first element's value.

        // Update elements to the left of the highest element found in vp.
        for (long long i = 0; i < vp[0].second; i++)
        {
            maxi = max(maxi, v[i]);
            v[i] = maxi;
        }
        
        maxi = v[n - 1]; // Reinitialize maxi with the last element's value.

        // Update elements to the right of the highest element found in vp.
        for (long long i = n - 1; i > vp[0].second; i--)
        {
            maxi = max(maxi, v[i]);
            v[i] = maxi;
        }

        long long sum = 0;

        // Calculate the sum of the modified array.
        for (long long i = 0; i < n; i++)
        {
            sum += v[i];
        }

        // Print the maximum sum for this test case.
        cout << sum << endl;
    }
    return 0;
}