Maximum Sum of Lengths of Non-Overlapping Subarrays with K as Max Element ใน C++

ปัญหา

มีอาร์เรย์และจำนวนเต็ม k หาผลรวมความยาวของ Subarray ที่ไม่ทับซ้อนกัน (non-overlapping) โดยที่ k เป็นค่าสูงสุดใน Subarray นั้น

ตัวอย่าง

array = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5}, k = 3
Subarrays: {3} len=1, {1,2,3,1} len=4, {3,2} len=2
Sum = 1+4+2 = 7

อัลกอริทึม

1. วนอ่านอาร์เรย์ ดัชนี i
2. นับ subarrayLength ต่อเนื่องที่ทุกค่า ≤ k
3. ถ้ามีค่า == k ใน subarray นั้น → flag = 1
4. จบ subarray: ถ้า flag=1 → lengthSum += subarrayLength
5. ข้ามค่าที่ > k

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

#include <iostream>
using namespace std;

int subArrayLengthSum(int arr[], int n, int k){
    int lengthSum = 0;
    int subarrayLength = 0;
    int flag = 0;
    for (int i = 0; i < n;) {
        subarrayLength = 0;
        flag = 0;
        while (arr[i] <= k && i < n) {
            subarrayLength++;
            if (arr[i] == k) flag = 1;
            i++;
        }
        if (flag == 1) lengthSum += subarrayLength;
        while (arr[i] > k && i < n) i++;
    }
    return lengthSum;
}

int main(){
    int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int ans = subArrayLengthSum(arr, size, k);
    cout << "The max sum of lengths of non-overlapping subarrays with " << k << " as max element is " << ans;
    return 0;
}

ผลลัพธ์

The max sum of lengths of non-overlapping subarrays with 3 as max element is 7