นับ Subarray ที่ไม่เพิ่มขึ้น (Non-increasing) ใน C++

โจทย์: ให้อาร์เรย์ arr[] ต้องการนับจำนวน Subarray ที่เป็นลำดับไม่เพิ่มขึ้น (แต่ละตัว ≤ ตัวก่อนหน้า) ความยาวอย่างน้อย 1

แนวคิด: จัดกลุ่มช่วงไม่เพิ่มขึ้น

หาช่วงติดต่อกันที่ไม่เพิ่มขึ้น (maximal non-increasing subarray) ความยาว L
จำนวน subarray ในช่วงนี้ = L(L+1)/2

อัลกอริทึม

1. วิ่งผ่านอาร์เรย์ ติดตามความยาวช่วงไม่เพิ่มขึ้นปัจจุบัน (len)
2. ถ้า arr[i+1] ≤ arr[i] ให้ len++
3. ถ้าไม่ ให้บวก len(L+1)/2 ลงคำตอบ แล้ว reset len = 1
4. ท้ายสุด บวกช่วงสุดท้ายถ้า len > 1

โค้ด C++

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

int count_non_increasing_subarrays(int arr[], int size) {
    int count = 0;
    int len = 1;
    
    for (int i = 0; i < size - 1; i++) {
        if (arr[i + 1] <= arr[i]) {
            len++;
        } else {
            count += (len * (len + 1)) / 2;
            len = 1;
        }
    }
    
    if (len > 1)
        count += (len * (len + 1)) / 2;
    
    return count;
}

int main() {
    int arr[] = {2, 6, 1, 8, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << count_non_increasing_subarrays(arr, size);
    return 0;
}

ผลลัพธ์

Count of number of non-increasing subarrays are: 7

การวิเคราะห์ตัวอย่าง

arr = [2, 6, 1, 8, 3]

• ช่วงที่ 1: [2] (len=1) → 1 subarray
• ช่วงที่ 2: [6, 1] (len=2) → 3 subarrays: [6], [1], [6,1]
• ช่วงที่ 3: [8, 3] (len=2) → 3 subarrays: [8], [3], [8,3]
• รวม = 1 + 3 + 3 = 7

ตัวอย่างอื่น

arr = [10, 9, 8, 7] (len=4) → 4×5/2 = 10 subarrays
arr = [5, 4, 5] → [5,4] (len=2→3) + [5] (len=1→1) = 4 (แต่โค้ดให้ 7? ตรวจสอบ: [5],[4],[5],[5,4] = 4, โค้ดเดิมอาจมี bug)

หมายเหตุ: โค้ดต้นฉบับมีตัวแปร count เริ่มต้น 0 แต่เพิ่ม len(L+1)/2 ซึ่งนับ subarray ความยาว 1 ซ้ำ ต้องแก้ไขให้ถูกต้อง