Maximize the Beauty Score of a Jogging Route

You are given a street with n sights, with sight number i being i miles from the beginning of the street. Sight number i has beauty bi. You want to start your morning jog l miles and end it r miles from the beginning of the street. By the time you run, you will see sights you run by (including sights at l and r miles from the start). You are interested in the 3 most beautiful sights along your jog, but every mile you run, you get more and more tired.

So choose l and r, such that there are at least 3 sights you run by, and the sum of beauties of the 3 most beautiful sights minus the distance in miles you have to run is maximized. More formally, choose l and r, such that bi1+bi2+bi3−(r−l) is maximum possible, where i1,i2,i3 are the indices of the three maximum elements in range [l,r].

Input The first line contains a single integer t (1≤t≤10⁵) — the number of test cases.

The first line of each test case contains a single integer n (3≤n≤10⁵).

The second line of each test case contains n integers bi (1≤bi≤10⁸) — beauties of sights i miles from the beginning of the street.

It's guaranteed that the sum of all n does not exceed 10⁵.

Output For each test case output a single integer equal to the maximum value bi1+bi2+bi3−(r−l) for some running range [l,r].

Example

inputCopy
4
5
5 1 4 2 3
4
1 1 1 1
6
9 8 7 6 5 4
7
100000000 1 100000000 1 100000000 1 100000000
outputCopy
8
1
22
299999996

Solution

Algorithm 1 (Monotone Queue)

Time Complexity: O(n)

We can think of a brute-force approach by iterating over all possible starting and ending points (l and r). For each pair, we would find the three most beautiful sights within the range [l,r] and calculate the corresponding beauty score. This solution would have a time complexity of O(n³), which is too slow.

To optimize this, we can observe that for each ending point r, we need to find the three most beautiful sights within the range [l,r]. We can use a monotone queue to maintain the three most beautiful sights in constant time. This way, for each r, we can calculate the beauty score in constant time. The overall time complexity is then reduced to O(n).

Algorithm 2 (Brute Force)

Time Complexity: O(n³)

This approach simply iterates through all possible combinations of l and r, calculating the beauty score for each combination. This results in a time complexity of O(n³), which is too slow for large values of n.

Code

Python3

# Implementation using Monotone Queue
def max_beauty_score(n, b):
    q = []  # Monotone queue to store the three most beautiful sights
    max_score = -float('inf')
    for i in range(n):
        # Add current sight to the queue
        while q and b[q[-1]] <= b[i]:
            q.pop()
        q.append(i)
        # Remove elements outside the range [*l,r*] from the queue
        while q and q[0] < i - 3:
            q.pop(0)
        # Calculate beauty score if there are at least 3 elements in the queue
        if len(q) >= 3:
            max_score = max(max_score, b[q[0]] + b[q[1]] + b[q[2]] - (i - q[0]))
    return max_score

t = int(input())
for _ in range(t):
    n = int(input())
    b = list(map(int, input().split()))
    print(max_beauty_score(n, b))

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int max_beauty_score(int n, vector<int> &b) {
    deque<int> q; // Monotone queue to store the three most beautiful sights
    int max_score = -1e9;
    for (int i = 0; i < n; ++i) {
        // Add current sight to the queue
        while (!q.empty() && b[q.back()] <= b[i]) {
            q.pop_back();
        }
        q.push_back(i);
        // Remove elements outside the range [*l,r*] from the queue
        while (!q.empty() && q.front() < i - 3) {
            q.pop_front();
        }
        // Calculate beauty score if there are at least 3 elements in the queue
        if (q.size() >= 3) {
            max_score = max(max_score, b[q[0]] + b[q[1]] + b[q[2]] - (i - q[0]));
        }
    }
    return max_score;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> b(n);
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
        }
        cout << max_beauty_score(n, b) << endl;
    }
    return 0;
}