C++-এ বেস্ট টাইম টু বাই অ্যান্ড সেল স্টক IV (Best Time to Buy and Sell Stock IV)

বেস্ট টাইম টু বাই অ্যান্ড সেল স্টক IV সমস্যা

একটি স্টক প্রাইস অ্যারে দেওয়া আছে। সর্বোচ্চ k ট্রানজ্যাকশন (বাই+সেল) করতে পারবেন। সর্বোচ্চ লাভ বের করতে হবে। একই সময়ে একাধিক স্টক ধরে রাখা যাবে না।

উদাহরণ: prices=[3,2,6,4,0,3], k=2 → লাভ ৭ (বাই ডে ২ সেল ডে ৩: ৪, বাই ডে ৫ সেল ডে ৬: ৩)

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং + অপ্টিমাইজেশন)

• যদি k >= n/2: অনলিমিটেড ট্রানজ্যাকশন মনে করে সব আপওয়ার্ড ট্রেন্ড যোগ করুন (O(n))
• অন্যথায় ৩D DP: dp[i][k][hold] = দিন i-তে k ট্রানজ্যাকশন বাকি থাকা অবস্থায় সর্বোচ্চ লাভ (hold=০/১ ধরে আছে/নাই)
• রিকার্সন + মেমোইজেশন বা বটম-আপ DP
• ট্রানজিশন:
  • হোল্ড না থাকলে:.skip বা বাই (hold=1, k-1)
  • হোল্ড থাকলে:.skip বা সেল (hold=0)

C++ কোড উদাহরণ

{3,2,6,4,0,3}

আউটপুট

7