ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে আছে; আমাদের একটি অ-খালি সাবারে (সংলগ্ন উপাদান) জন্য সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে সর্বাধিক একটি উপাদান মুছে ফেলা হয়। অন্য কথায়, আমরা বলতে পারি যে আমরা একটি সাব্যারে বেছে নিতে চাই এবং ঐচ্ছিকভাবে এটি থেকে একটি উপাদান মুছে ফেলতে চাই যাতে এখনও অন্তত একটি উপাদান অবশিষ্ট থাকে এবং অবশিষ্ট উপাদানগুলির যোগফল সর্বাধিক সম্ভব হয়। আমাদের মনে রাখতে হবে যে একটি উপাদান মুছে ফেলার পরে সাবারেটি খালি না হওয়া দরকার। সুতরাং যদি ইনপুটটি [1,-2,0,3] এর মত হয়, তাহলে আউটপুট হবে 4। তাই যদি আমরা -2 মুছে ফেলি, এটি সর্বোচ্চ যোগফল প্রদান করবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=অ্যারের আকার, এবং :=a[0]
- suff_with_del :=0, suff_with_out_del :=a[0]
- এর জন্য i রেঞ্জ i থেকে n – 1
- suff_with_del :=সর্বাধিক suff_with_del + a[i] এবং suff_with_out_del
- suff_with_out_del :=a[i] এর সর্বোচ্চ এবং suff_with_out_del + a[i]
- উত্তর :=উত্তরের সর্বোচ্চ, suff_with_out_del এবং suff_with _del
- রিটার্ন রিটার্ন
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumSum(vector<int>& a) {
int n = a.size();
int ans = a[0];
int suffix_with_deletion = 0;
int suffix_with_not_deletion = a[0];
for(int i = 1;i<n;i++){
suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_with_not_deletion);
suffix_with_not_deletion = max(a[i],suffix_with_not_deletion+a[i]);
ans = max({ans, suffix_with_not_deletion,suffix_with_deletion});
}
return ans;
}
};
main(){
vector<int> v = {1,-2,0,3};
Solution ob;
cout <<ob.maximumSum(v);
} ইনপুট
[1,-2,0,3]
আউটপুট
4
