পাইথনে একটি 'বৈধ' অ্যারের সর্বাধিক মান খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন, আমাদের n পূর্ণসংখ্যার 'সংখ্যা' এর একটি অ্যারে আছে। 'সংখ্যা' এর প্রতিটি মান তার 'শক্তি' উপস্থাপন করে। অ্যারের দৈর্ঘ্য দুইটির বেশি হলে এবং অ্যারের প্রথম ও শেষ মান সমান হলে অ্যারের 'বৈধ' মূল্যায়ন করা হবে। আমাদের অ্যারে থেকে উপাদানগুলি মুছে দিয়ে অ্যারেটিকে বৈধ করতে হবে যাতে বাকিরা শর্তটি পূরণ করতে পারে। আউটপুট হিসাবে, আমরা অ্যারের সমস্ত পাওয়ার মান যোগ করে অ্যারের সর্বাধিক সম্ভাব্য পাওয়ার মান ফেরত দিই।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[3, 4, 5, 3, 4], তাহলে আউটপুট হবে 16।

যদি আমরা অ্যারের সংখ্যা থেকে প্রথম মান 3 মুছে ফেলি, তাহলে এটি [4, 5, 3, 4] হয়ে যায়। এটি একটি বৈধ অ্যারে এবং পাওয়ারগুলির যোগফল হল 4 + 5 + 3 + 4 =16৷ এটি প্রদত্ত ইনপুট থেকে যেকোনো বৈধ অ্যারের জন্য সর্বাধিক সম্ভাব্য যোগফল৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• টেবিল :=একটি নতুন মানচিত্র

• উপসর্গ :=মান 0

  সহ একটি নতুন তালিকা আরম্ভ করা হয়েছে

• নেতিবাচক :=0

  মান সহ একটি নতুন তালিকা শুরু হয়েছে

• প্রতিটি সূচকের জন্য i এবং মান j সংখ্যায়, করুন

  • যদি j টেবিলে উপস্থিত না থাকে, তাহলে

    • টেবিল[j] :=একটি নতুন জোড়া (i, 0)

    • অন্যথায়,

      • টেবিল[j, -1] :=i

    • উপসর্গে একটি নতুন উপাদান যোগ করুন যা উপসর্গ + j

      এর শেষ উপাদানের সমান

    • নেগেটিভের শেষ উপাদানটির নকল করুন

    • যদি j <0 , তারপর

      • ঋণাত্মক এর শেষ উপাদান :=ঋণাত্মক + j

        এর শেষ উপাদান

• উত্তর :=ঋণাত্মক অসীম

• টেবিলের সকল মানের প্রতিটি জোড়ার (i,j) জন্য, করুন

  • যদি j 0 এর মত না হয়, তাহলে

    • sm1 :=উপসর্গ[j+1] - উপসর্গ[i]

    • যদি j> i+1 হয়, তাহলে

      • sm2 :=নেতিবাচক[j] - নেতিবাচক[i+1]

    • অন্যথায়,

      • sm2 :=0

    • ans :=সর্বাধিক (ans, sm1 - sm2)

• উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(nums):
   table = {}
   prefix = [0]
   negative = [0]
   for i, j in enumerate(nums):
      if j not in table:
         table[j] = [i, 0]
      else:
         table[j][-1] = i
      prefix += prefix[-1] + j,
      negative += negative[-1],
      if j < 0:
         negative[-1] += j

   ans = float('-inf')
   for i,j in table.values():
      if j != 0:
         sm1 = prefix[j+1] - prefix[i]
         sm2 = negative[j] - negative[i+1] if j > i+1 else 0
         ans = max(ans, sm1 - sm2)
   return ans

print(solve([3, 4, 5, 3, 4]))

ইনপুট

[3, 4, 5, 3, 4]

আউটপুট

16