C++ Số mảng con có min và max bằng nhau

Tìm số mảng con mà phần tử nhỏ nhất và lớn nhất bằng nhau (tức là mọi phần tử trong mảng con đều bằng nhau). Ví dụ:

Input: {2,3,6,6,2,4,4,4} → Output: 12
Mảng con: {2},{3},{6},{6},{2},{4},{4},{4},{6,6},{4,4},{4,4},{4,4,4}

Input: {3,3,1,5,1,2,2} → Output: 9

Phương pháp O(n²)

Với mỗi i, đếm số phần tử liên tiếp bằng a[i] từ i+1 trở đi. Kết quả = n + tổng count.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[]={2,4,5,3,3,3}, n=sizeof(a)/sizeof(a[0]);
    int result=n, count=0;
    for (int i=0; i

Kết quả
Số mảng con min=max: 9

Phương pháp hiệu quả O(n)
Nhóm các dãy liên tiếp cùng giá trị. Với nhóm độ dài k, số mảng con = k(k+1)/2. Tổng over all groups.

Ví dụ
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[]={2,4,5,3,3,3}, n=sizeof(a)/sizeof(a[0]);
    int result=0, count=1, temp=a[0];
    for (int i=1; i

Kết quả
Số mảng con min=max: 9

Kết luận
Đã giải bài toán mảng con min=max bằng 2 cách: O(n²) kiểm tra liên tiếp và O(n) nhóm dãy cùng giá trị + công thức k(k+1)/2. Hy vọng hữu ích.