สมมติว่าเรามีอาร์เรย์ A และเราต้องหาจำนวนทั้งหมดของอาร์เรย์ย่อยที่มีความยาวลดลง> 1 อย่างเคร่งครัด ดังนั้นถ้า A =[100, 3, 1, 15] ลำดับที่ลดลงคือ [100, 3], [100, 3, 1], [15] ดังนั้นเอาต์พุตจะเป็น 3 เมื่อพบอาร์เรย์ย่อยสามชุด
แนวคิดคือ find subarray ของ len l และเพิ่ม l(l – 1)/2 เพื่อให้ได้ผลลัพธ์
ตัวอย่าง
#include<iostream>
using namespace std;
int countSubarrays(int array[], int n) {
int count = 0;
int l = 1;
for (int i = 0; i < n - 1; ++i) {
if (array[i + 1] < array[i])
l++;
else {
count += (((l - 1) * l) / 2);
l = 1;
}
}
if (l > 1)
count += (((l - 1) * l) / 2);
return count;
}
int main() {
int A[] = { 100, 3, 1, 13, 8};
int n = sizeof(A) / sizeof(A[0]);
cout << "Number of decreasing subarrys: " << countSubarrays(A, n);
} ผลลัพธ์
Number of decreasing subarrys: 4
