Temperature

Problem Statement

• English
• French
• Arabic

Solution

We have the values of and we want to compute the values of as follows:

Once we compute the values of , we want the final answer:

---

Subtask 1 & 2: 60 points

We can use two nested loops and find the maximum among all pairs in the array .

---

Subtask 3: 100 points

To maximize the answer for any from 1 to , we need to subtract it from the minimum value in the range . We can maintain this minimum value while iterating.

Let:

• mn = minimum value seen so far (initially ).

• mx = best answer so far (initially 0)

For each :

• .

• .

At the end, the answer is in mx.

Print mx and congrats, you got 100 points!

Implementation

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin >> n;
    vector<ll> a(n+1, 0);
    for(ll i = 1; i <= n; i++) cin >> a[i];
    ll mini = 0;
    ll current = 0;
    ll res = 0;
    for(auto t : a){
        current += t;
        res = max(res, current - mini);
        mini = min(current, mini);
    }
    cout << res << '\n';

}