মনে করুন একটি পূর্ণসংখ্যার অ্যারে আছে, আমাদের একটি নন-ইম্পটি সাবঅ্যারে (কন্টিগুয়াস এলিমেন্ট) এর সর্বোচ্চ সম বের করতে হবে যেখানে শুধু একটি এলিমেন্ট ডিলিট করার সুযোগ আছে। অন্য কথায়, আমরা একটি সাবঅ্যারে বেছে নেব এবং ঐচ্ছিকভাবে সেটি থেকে একটি এলিমেন্ট ডিলিট করব যাতে কমপক্ষে একটি এলিমেন্ট বাঁচে থাকে এবং বাঁচা এলিমেন্টগুলোর সম সর্বোচ্চ হয়। মনে রাখতে হবে সাবঅ্যারে এক এলিমেন্ট ডিলিট করার পরও নন-ইম্পটি থাকতে হবে। যদি ইনপুট `[1,-2,0,3]` হয়, তবে আউটপুট হবে ৪। যদি আমরা -2 ডিলিট করি, তবে সর্বোচ্চ সম পাওয়া যাবে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- `n` := অ্যারের আকার, `ans := a[0]`
- `suff_with_del := 0`, `suff_with_out_del := a[0]`
- `i` = 1 থেকে `n-1` পর্যন্ত
- `suff_with_del := max(suff_with_del + a[i], suff_with_out_del)`
- `suff_with_out_del := max(a[i], suff_with_out_del + a[i])`
- `ans := max(ans, suff_with_out_del, suff_with_del)`
- `res` রিটার্ন করুন
উদাহরণ (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
