UWCOI20A - Peak Finding - Editorial

A. Peak Finding

Practice
UWCOI2020

Author: Jishnu Roychoudhury (astoria)
Tester: Taranpreet Singh (taran_1407)
Editorialist: Jishnu Roychoudhury (astoria)

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Find the maximum value in an array.

QUICK EXPLANATION:

Iterate through the array storing a maximum value in O(N).

EXPLANATION:

Initialise a “maximum so far” variable to 0. Use a for loop to iterate through the array. For each array element, set the “maximum so far” variable to the maximum of itself and the array element. Output the “maximum so far” variable at the end.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

void sol(){
    int n;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++) cin >> a[i];
    int mx = 0;
    for (int i=0; i<n; i++){
        mx = max(mx, a[i]);
    }
    cout << mx << endl;
}

int main(){
    int t; cin >> t; while(t--) sol();
}

If the JSA is allowed to succeed, they will use the combined power of the WQS binary search and the UFDS to take over the world!

What does this statement in the question indicate ? I though we must use binary search for answering the problem.

In response to @krish_na,

@astoria’s favourite technique is the “WQS binary search” and @socho’s (my) favourite data structure is the “Union Find Disjoint Set (UFDS)”. We added that line as a part of the story, it’s not the solution to this task :slight_smile: