Set of Pairs program in C++

Question

I am making a set of pairs of Max and Min elements of Every Subset in an Array.But its giving me these errors. And at last I need Size of set. (Edited with some suggestions)

In function 'int main()':

27:12: error: 'max_element' was not declared in this scope

27:12: note: suggested alternative: 'max_align_t'

28:12: error: 'min_element' was not declared in this scopeIn function 'int main()':

Code:

#include <iostream>
#include <set>
#include <vector>
#include <utility>


typedef std::pair<int,int> pairs;

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int n, max, min;
    
    set<pairs> s;
    
    cin >> n;

    int a[n];
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    for(int i=0;i<n;i++) {
        for(int j=i;j<n;j++) {
            vector<int> v;
            v.push_back(a[j]);
            if(v.size() > 1) {
                max = *max_element(v.begin(),v.end());
                min = *min_element(v.begin(),v.end());
                pairs p1 = make_pair(max, min);
                s.insert(p1);
                max = 0; 
                min = 0;
            }
            
        }
    }
    cout << s.size() << endl;
    
}

Answer 1

typedef pair<int,int> pairs;

should be

typedef std::pair<int,int> pairs;

(Or you could move using namespace std; so that it is before your typedef).

Plus typedefing a single pair as the plural pairs is a really really bad idea, that is going to confuse you and anyone else reading your code for the rest of this programs existence. If you want a typedef for a pair of ints, then call it that

typedef std::pair<int,int> pair_of_ints;

Answer 2

To make your last programme works, it was needed to move the declaration of std::vector<int> v;

Moreover, your code has a complexity O(n^3). In practice, it is possible to get a complexity O(n^2), by calculating iteratively the max and min values.

This code compares your code and the new one. The results are identical. However, I cannot be sure that your original code does what you intended to do.

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>

typedef std::pair<int,int> pairs;

//using namespace std;

void print (const std::set<pairs> &s) {
    for (auto& p: s) {
        std::cout << "(" << p.first << ", " << p.second << ") ";
    }
    std::cout << "\n";
}

int count_pairs_op (const std::vector<int>& a) {
    int max, min;
    int n = a.size();
    std::set<pairs> s;

   for(int i = 0; i < n; i++) {
       std::vector<int> v;
       for(int j = i; j < n; j++) {
            v.push_back(a[j]);
            if(v.size() > 1) {
                max = *std::max_element(v.begin(), v.end());
                min = *std::min_element(v.begin(), v.end());
                pairs p1 = std::make_pair(max, min);
                s.insert(p1);
            }
        }
    }
    print (s);  
    return s.size();
}

int count_pairs_new (const std::vector<int>& a) {
    int max, min;
    int n = a.size();
    std::set<pairs> s;

   for(int i = 0; i < n; i++) {
       min = a[i];
       max = a[i];
       for(int j = i+1; j < n; j++) {
            max = std::max (max, a[j]);
            min = std::min (min, a[j]);
            pairs p1 = std::make_pair(max, min);
            s.insert(p1);
        }
    }
    print (s);  
    return s.size();
}

int main() {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for(int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::cout << count_pairs_op(a) << std::endl;
    std::cout << count_pairs_new(a) << std::endl;
    
}

---

It appears that there was a mistake in the understanding of the problem. For each subarray, we have to consider the maximum and the second maximum. Moreover, we know that all elements are distinct.
As the size can be up to 10^5, we have to look for a complexity smaller than O(n^2).

In practice, each element can be the second element of two subarrays, if there exist a greater element before and after it. We just have to check it.

This can be perfomed by calculating, for each index i, the maximum value before and after it.

Total complexity: O(n)

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>

int count_pairs_2nd_max (const std::vector<int>& a) {
    int n = a.size();
    int count = 0;
    std::vector<int> max_up(n), max_down(n);
    max_up[0] = -1;
    for (int i = 1; i < n; ++i) {
        max_up[i] = std::max(max_up[i-1], a[i-1]);
    }
    max_down[n-1] = -1;
    for (int i = n-2; i >= 0; --i) {
        max_down[i] = std::max(max_down[i+1], a[i+1]);
    }
    
    for(int i = 0; i < n; ++i) {
        if (max_up[i] > a[i]) count++;
        if (max_down[i] > a[i]) count++;
    }
    return count;
}

int main() {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for(int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::cout << count_pairs_2nd_max(a) << std::endl;
    
}