นับซับอาเรย์ที่ค่าสูงสุดมากกว่า k ใน C++

เราได้รับอาเรย์ arr[] ที่มีสมาชิกจำนวนเต็มและตัวแปร k เป้าหมายคือหาจำนวนซับอาเรย์ของ arr[] ที่มีค่าสูงสุด/สูงสุดมากกว่า k หากอาเรย์คือ [1,2,3] และ k เป็น 1 ซับอาเรย์ที่เป็นไปได้คือ [1], [2], [3], [1,2], [2,3], [1,2,3] ซับอาเรย์ที่มีค่าสูงสุด > 1 คือ [2], [3], [1,2], [2,3], [1,2,3] จำนวนคือ 5

มาดูตัวอย่าง

อินพุต − arr[] = {1,2,5,3 } k=3

เอาต์พุต − จำนวนซับอาเรย์ที่ค่าสูงสุดมากกว่า k คือ 6

คำอธิบาย − ซับอาเรย์ทั้งหมดคือ [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3] ซับอาเรย์ที่มีค่าสูงสุดมากกว่า 3 คือที่มี 5 อยู่ ได้แก่ [5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3] รวม 6 ซับอาเรย์

อินพุต − arr[] = {1,2,3,4,5 } k=4

เอาต์พุต − จำนวนซับอาเรย์ที่ค่าสูงสุดมากกว่า k คือ 5

คำอธิบาย − ตัวเลขที่มากกว่า 4 มีแค่ 5 ซับอาเรย์ที่มี 5 คือ [5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5] รวม 5 ซับอาเรย์

แนวทางที่ใช้ในโปรแกรม

ในแนวทางนี้เรารู้ว่าจำนวนซับอาเรย์ทั้งหมดของอาเรย์ n สมาชิกคือ n*(n+1)/2

เราจะมองหาซับอาเรย์ที่มีสมาชิก < k โดยข้ามสมาชิก >k และนับความยาวของซับอาเรย์ที่สมาชิกทั้งหมดน้อยกว่า k สำหรับความยาว l แต่ละซับอาเรย์สร้างได้ l*(l+1)/2 ซับอาเรย์ บวกค่านี้สำหรับซับอาเรย์แต่ละอันเป็น X ท้ายสุดลบ X ออกจาก n*(n+1)/2 เพื่อได้ผลลัพธ์ที่ต้องการ

• รับอาเรย์จำนวนเต็ม arr[] และตัวแปร k
• ฟังก์ชัน maximum_k(int arr[], int size, int k) รับอาเรย์, k, ความยาว คืนจำนวนซับอาเรย์ที่ค่าสูงสุดมากกว่า k
• กำหนด count เริ่มต้น 0
• ใช้ลูป while เดินทางอาเรย์จากดัชนี i=0 ถึง i<size
• สำหรับแต่ละสมาชิกถ้า arr[i]>k ข้ามด้วย continue
• มิฉะนั้น เริ่มนับความยาวซับอาเรย์ด้วยลูป while ภายใน
• ถ้า arr[i]<k และ i<size เพิ่ม i และ temp (ความยาวซับอาเรย์ที่สมาชิกทั้งหมด < k)
• ท้ายสุดของลูปภายใน ได้ความยาวซับอาเรย์ปัจจุบันเป็น temp คำนวณ temp*(temp+1)/2 บวกเข้า count
• ทำซ้ำสำหรับซับอาเรย์ทุกอัน
• ท้ายสุดของลูปนอก มีตัวแปร count เป็นจำนวนซับอาเรย์ทั้งหมดที่สมาชิก < k
• อัปเดต count โดยลบ count นี้ออกจากจำนวนซับอาเรย์ทั้งหมดของ arr[] คือ size*(size-1)/2
• คืน count

ตัวอย่างโค้ด C++

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

int maximum_k(int arr[], int size, int k){
    int count = 0;
    int i = 0;
    while (i < size){
        if (arr[i] > k){
            i++;
            continue;
        }
        int temp = 0;
        while (i < size && arr[i] <= k){
            i++;
            temp++;
        }
        int temp_2 = temp * (temp + 1);
        count = count + temp_2 / 2;
    }
    count = (size * (size + 1) / 2 - count);
    return count;
}

int main(){
    int arr[] = { 4, 1, 2, 7, 8, 3 };
    int k = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of subarrays whose maximum element is greater than k are: "<<maximum_k(arr, size, k);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of subarrays whose maximum element is greater than k are: 14