একটি ইন্টিজার অ্যারে দেওয়া আছে। এর সব কন্টিগুয়াস সাবঅ্যারে বের করে একটি লিস্টে রাখা হয়। প্রতিটি সাবঅ্যারেকে তার সর্বোচ্চ এলিমেন্ট দিয়ে রিপ্লেস করা হয়। একটি সংখ্যা k দেওয়া আছে। কতগুলো সাবঅ্যারে এখন k-র চেয়ে বড় সেটা বের করতে হবে।
ইনপুট: input_array = [5, 6, 7, 8], k = 7 → আউটপুট: 4।
সাবঅ্যারে: {5},{6},{7},{8},{5,6},{6,7},{7,8},{5,6,7},{6,7,8},{5,6,7,8}
ম্যাক্সimum দিয়ে রিপ্লেস: {5},{6},{7},{8},{6},{7},{8},{7},{8},{8}
৭ থেকে বড়: ৪টি (৮,৮,৮,৮)।
সমাধানের ধাপসমূহ (O(n) সময়ে)
count := 0, consecutive := 0
input_array-এর প্রতিটি x-এর জন্য:
- যদি x > k: consecutive = 0
- অন্যথায়: consecutive++, count += consecutive
টোটাল সাবঅ্যারে = n*(n+1)//2
উত্তর = টোটাল সাবঅ্যারে - count
উদাহরণ (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))
ইনপুট
[5, 6, 7, 8], 7
আউটপুট
4
