মনে করুন nums নামে একটি অ্যারে এবং k নামে একটি মান আছে। একটি সাবঅ্যার (i, j)-র স্কোর সংজ্ঞায়িত হল subarray nums[i..j]-এর ন্যূনতম * (j-i+1)। এখন, একটি ভালো সাবঅ্যার হল এমন একটি সাবঅ্যার যেখানে i <= k <= j। আমাদের একটি ভালো সাবঅ্যারের সর্বোচ্চ সম্ভাব্য স্কোর বের করতে হবে।
সুতরাং, যদি ইনপুট হয় nums = [2,5,4,8,5,6], k = 3, তবে আউটপুট হবে 20 কারণ অপ্টিমাল সাবঅ্যার এখানে (1, 5), তাই nums[1..5]-এর ন্যূনতম 4, সুতরাং 4*(5-1+1) = 20
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
ans := nums[k], minNum := nums[k]
i := k, j := k
যতক্ষণ i > -1 বা j < nums-এর আকার, করুন
যতক্ষণ i > -1 এবং nums[i] >= minNum, করুন
i := i - 1
যতক্ষণ j < nums-এর আকার এবং nums[j] >= minNum, করুন
j := j + 1
ans := ans এবং ((j - i - 1) * minNum) এর মধ্যে সর্বোচ্চ
minNum := (nums[i] যদি i > -1 অন্যথায় -1) এবং (nums[j] যদি j < nums-এর আকার অন্যথায় -1) এর মধ্যে সর্বোচ্চ
ans রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
def solve(nums, k):
ans = nums[k]
minNum = nums[k]
i = k
j = k
while i > -1 or j < len(nums):
while i > -1 and nums[i] >= minNum:
i -= 1
while j < len(nums) and nums[j] >= minNum:
j += 1
ans = max(ans, (j - i - 1) * minNum)
minNum = max(nums[i] if i > -1 else -1, nums[j] if j < len(nums) else -1)
return ans
nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))
ইনপুট
[2,5,4,8,5,6], 3
আউটপুট
20
