पायथन में एक अच्छे सबअरे का अधिकतम स्कोर खोजने का कार्यक्रम

मान लीजिए कि हमारे पास nums नामक एक सरणी है और एक मान k है। एक सबअरे के स्कोर पर विचार करें (i, j) को न्यूनतम सबअरे अंकों के रूप में परिभाषित किया गया है [i..j] * (j-i + 1)। अब, एक अच्छा सबअरे एक सबअरे है जहाँ i <=k <=j. हमें एक अच्छे सबअरे का अधिकतम संभव स्कोर खोजना होगा।

इसलिए, यदि इनपुट अंकों की तरह है =[2,5,4,8,5,6] k =3, तो आउटपुट 20 होगा क्योंकि इष्टतम उपसरणी यहाँ (1, 5) है, इसलिए न्यूनतम संख्या [1] ..5] 4 है, इसलिए 4*(5-1+1) =20

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

उत्तर:=अंक [के], न्यूनतम संख्या:=अंक [के]
मैं:=के, जे:=के
जबकि i> -1 या j <अंकों का आकार, करें
- जबकि मैं> -1 और अंक [i]>=न्यूनतम संख्या, करें
  - मैं :=मैं - 1
- जबकि j <अंकों और अंकों का आकार [j]>=minNum, do
  - जे:=जे + 1
- उत्तर:=अधिकतम उत्तर और ((j - i - 1) * न्यूनतम संख्या)
- न्यूनतम संख्या:=अधिकतम (अंक [i] यदि i> -1 अन्यथा -1) और (अंक [j] यदि j <अंकों का आकार अन्यथा -1)
वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

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