เราได้รับอาร์เรย์ 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
ตอนนี้เราจะมองหาอาร์เรย์ย่อยที่มีองค์ประกอบ
-
รับอาร์เรย์จำนวนเต็ม arr[] และตัวแปร k เป็นอินพุต
-
ฟังก์ชัน maximum_k(int arr[], int size, int k) ใช้อาร์เรย์ k และความยาวของอาร์เรย์และส่งกลับจำนวนอาร์เรย์ย่อยที่มีองค์ประกอบสูงสุดมากกว่า k
-
นับเริ่มต้นเป็น 0
-
ใช้ while loop เลื่อนอาร์เรย์จาก index i=0 ถึง i
-
สำหรับแต่ละองค์ประกอบถ้า arr[i]>k ข้ามโดยใช้คำสั่งดำเนินการต่อไป
-
อย่างอื่นเริ่มนับความยาวของ subarray โดยใช้ inner while loop
-
ถ้า arr[i]
-
ที่ส่วนท้ายของ inner ในขณะที่เรามีความยาวของ subarray ปัจจุบันเป็น temp.
คำนวณ temp*(temp+)/2 แล้วบวกเพื่อนับ
-
ทำเช่นนี้กับอาร์เรย์ย่อยทั้งหมด
-
ที่ปลายด้านนอกในขณะที่ เรามีตัวแปรนับเป็นจำนวนอาร์เรย์ย่อยทั้งหมดที่มีองค์ประกอบ
-
อัปเดตการนับโดยลบจำนวนนี้ออกจากจำนวนอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดของ arr[] นั่นคือ size*(size-1)/2
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#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
