โปรแกรม C++ หาจำนวนซับอาร์เรย์ที่ลดลงอย่างเคร่งครัด (Strictly Decreasing Subarrays)

สมมติว่าเรามีอาร์เรย์ A และเราต้องหาจำนวนรวมของซับอาร์เรย์ที่ลดลงอย่างเคร่งครัดที่มีความยาว > 1 ดังนั้นถ้า A = [100, 3, 1, 15] ลำดับที่ลดลงคือ [100, 3], [100, 3, 1], [15] ผลลัพธ์จะเป็น 3 เนื่องจากพบซับอาร์เรย์ 3 ตัว

แนวคิดคือหาซับอาร์เรย์ที่มีความยาว l และเพิ่ม l(l-1)/2 ไปยังผลลัพธ์

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

#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