โปรแกรมหาจำนวน Subarray ที่ Max มากกว่า k (Python)

โจทย์

มีอาร์เรย์ หา Subarray ต่อเนื่องทั้งหมด แทนแต่ละ Subarray ด้วยค่า Max ภายใน มีค่า k ให้หาว่ามี Subarray กี่อันที่ Max > k

ตัวอย่าง: input_array = [5,6,7,8], k = 7 → Subarrays Max: [5],[6],[7],[8],[6],[7],[8],[7],[8],[8] → มากกว่า 7 มี 4 อัน ([8],[8],[8],[8])

อัลกอริธึม (Complement Counting)

1. นับ Subarray ที่ Max ≤ k (คือ Subarray ที่ทุก Element ≤ k)
2. รวม Subarray ทั้งหมด = n(n+1)/2
3. คำตอบ = Total - Count(Max ≤ k)

โค้ด Python

def solve(input_array, k):
    count = 0
    consecutive = 0
    for x in input_array:
        if x > k:
            consecutive = 0
        else:
            consecutive += 1
            count += consecutive
    return len(input_array) * (len(input_array) + 1) // 2 - count

print(solve([5, 6, 7, 8], 7))  # Output: 4

Input / Output

Input:  [5, 6, 7, 8], 7
Output: 4