cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2016 · EasyArray extrema

Longest Extreme Subarray

National Olympiad — Municipal round (2016 season)

Submission name: red.cpp

Solve in Editor →

Problem summary

Find the longest contiguous subarray maximizing the absolute difference between its first and last values. Break ties by the smallest sum of endpoint indices.

Input

N and N positive integers.

Output

The 1-based first and last indices.

Constraints

1 < N ≤ 20000; values ≤ 1000000.

Worked example

An independently prepared example for this explanation.

Input

10
3 1 2 5 5 4 4 5 3 1

Output

2 8

Solution analysis

  1. The largest possible absolute endpoint difference is the global maximum minus the global minimum. Therefore endpoints must carry these two extremes, unless all values are equal.
  2. For each orientation, the longest choice uses the first occurrence of one extreme and the last occurrence of the other. Compare the resulting two intervals by length and then endpoint sum. When all values agree, choose the whole array.
  3. The minimum 1 occurs at 2 and 10, and the maximum 5 at 4,5,8. The two farthest opposite pairs are (2,8) and (4,10), both spanning seven values. Their index sums are 10 and 14, so choose 2 8.

Why it works

Any optimal endpoints have opposite extreme values. In either orientation, replacing the left endpoint by the earliest such extreme and the right endpoint by the latest other extreme cannot shorten the interval. Thus the two candidates include a longest optimum, and explicit tie comparison implements the requested rule.

Complexity: O(N) time and O(N) space for the array.

Watch out. Maximize endpoint difference before interval length. Equal values require the whole array.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: The largest possible absolute endpoint difference is the global maximum minus the
// global minimum.
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int&value:a){
        cin>>value;
    }
    int low=*min_element(a.begin(),a.end());
    int high=*max_element(a.begin(),a.end());
    int firstLow=n,lastLow=-1,firstHigh=n,lastHigh=-1;
    for(int i=0;i<n;++i){
        if(a[i]==low){
            firstLow=min(firstLow,i);
            lastLow=i;
        }
        if(a[i]==high){
            firstHigh=min(firstHigh,i);
            lastHigh=i;
        }
    }
    pair<int,int>best={min(firstLow,lastHigh),max(firstLow,lastHigh)};
    pair<int,int>other={min(firstHigh,lastLow),max(firstHigh,lastLow)};
    int bestLength=best.second-best.first;
    int otherLength=other.second-other.first;
    if(otherLength>bestLength||
        (otherLength==bestLength&&other.first+other.second<best.first+best.second)){
        best=other;
    }
    cout<<best.first+1<<' '<<best.second+1<<'\n';
}

Source: Arena Olimpiici ↗