मान लीजिए हमारे पास nums नामक एक सरणी और एक मान k है। उपसरणी (i, j) का स्कोर न्यूनतम उपसरणी 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