ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় nums এবং আরেকটি মান k, আমাদেরকে k আকারের প্রদত্ত তালিকার তিনটি নন-ওভারল্যাপিং সাবলিস্টের বৃহত্তম যোগফল খুঁজে বের করতে হবে।
সুতরাং, ইনপুট যদি nums =[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k =3 এর মত হয়, তাহলে আউটপুট হবে 27, যেমন আমরা নির্বাচন করতে পারি। সাবলিস্ট [2, 2, 2], [4, 4, 4], এবং [3, 3, 3], মোট যোগফল 27।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- P :=[0]
- এ প্রতিটি x এর জন্য, করুন
- P[-1] + P-এর শেষে x ঢোকান
- প্রশ্ন :=[P[i + K] - P[i] রেঞ্জ 0 থেকে P - K এর আকারের জন্য]
- উপসর্গ :=Q[সূচী ০ থেকে শেষ]
- প্রত্যয় :=Q[সূচী ০ থেকে শেষ]
- আমি 0 থেকে Q - 1 এর আকারের জন্য, কর
- উপসর্গ[i + 1] :=সর্বাধিক উপসর্গ[i + 1], উপসর্গ[i]
- প্রত্যয়[~(i + 1)] :=সর্বাধিক প্রত্যয়[~(i + 1)], প্রত্যয়[~i]
- ret =(Q[i] + উপসর্গ[i - K] + প্রত্যয়[i + K]) প্রতিটি i রেঞ্জের K থেকে Q - K - 1 এর আকারের জন্য
- সর্বোচ্চ রিটার্ন রিটার্ন
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
class Solution: def solve(self, A, K): P = [0] for x in A: P.append(P[-1] + x) Q = [P[i + K] - P[i] for i in range(len(P) - K)] prefix = Q[:] suffix = Q[:] for i in range(len(Q) - 1): prefix[i + 1] = max(prefix[i + 1], prefix[i]) suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i]) return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K)) ob = Solution() nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k = 3 print(ob.solve(nums, k))
ইনপুট
[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3
আউটপুট
27
