সর্বাধিক/সর্বনিম্ন যোগফলবিশিষ্ট সাবঅ্যারে অনুসন্ধান#

এখানে, আমরা সর্বাধিক যোগফলবিশিষ্ট সাবঅ্যারে খুঁজে বের করার সমস্যাটি বিবেচনা করব, সেইসাথে এর কিছু ভিন্নরূপ (এই সমস্যাটি অনলাইনে সমাধানের অ্যালগরিদমসহ)।

সমস্যার বিবৃতি#

একটি সংখ্যার অ্যারে $a[1 \ldots n]$ দেওয়া আছে। সর্বাধিক যোগফলবিশিষ্ট একটি সাবঅ্যারে $a[l \ldots r]$ খুঁজে বের করতে হবে:

$$ \max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].$$

উদাহরণস্বরূপ, যদি অ্যারে $a[]$-এর সমস্ত পূর্ণসংখ্যা অঋণাত্মক হয়, তাহলে উত্তর হবে সম্পূর্ণ অ্যারেটি। তবে, যখন অ্যারেতে ধনাত্মক এবং ঋণাত্মক উভয় সংখ্যা থাকতে পারে তখন সমাধানটি অতুচ্ছ।

এটা স্পষ্ট যে সর্বনিম্ন সাবঅ্যারে খুঁজে বের করার সমস্যাটি মূলত একই, শুধু সমস্ত সংখ্যার চিহ্ন পরিবর্তন করতে হবে।

অ্যালগরিদম ১#

এখানে আমরা একটি প্রায় সুস্পষ্ট অ্যালগরিদম বিবেচনা করি। (পরে, আমরা আরেকটি অ্যালগরিদম দেখব, যেটি বের করা একটু কঠিন, কিন্তু এর ইমপ্লিমেন্টেশন আরও ছোট।)

অ্যালগরিদমের বর্ণনা#

অ্যালগরিদমটি খুবই সরল।

সুবিধার জন্য আমরা সংকেত প্রবর্তন করি: $s[i] = \sum_{j=1}^{i} a[j]$। অর্থাৎ, অ্যারে $s[i]$ হলো অ্যারে $a[]$-এর আংশিক যোগফলের অ্যারে। এছাড়া, $s[0] = 0$ ধরি।

এখন আমরা ইনডেক্স $r = 1 \ldots n$ জুড়ে ইটারেট করি এবং প্রতিটি বর্তমান মান $r$-এর জন্য সেই সর্বোত্তম $l$ দ্রুত খুঁজে বের করতে শিখি, যেখানে সাবঅ্যারে $[l, r]$-এ সর্বাধিক যোগফল পাওয়া যায়।

আনুষ্ঠানিকভাবে, এর অর্থ হলো বর্তমান $r$-এর জন্য আমাদের এমন একটি $l$ ($r$-এর বেশি নয়) খুঁজে বের করতে হবে, যাতে $s[r] - s[l-1]$-এর মান সর্বাধিক হয়। একটি তুচ্ছ রূপান্তরের পর, আমরা দেখতে পাই যে আমাদের অ্যারে $s[]$-এ $[0, r-1]$ সেগমেন্টে সর্বনিম্ন খুঁজে বের করতে হবে।

এখান থেকে, আমরা তাৎক্ষণিকভাবে একটি সমাধান পাই: আমরা কেবল অ্যারে $s[]$-এ বর্তমান সর্বনিম্ন কোথায় আছে তা সংরক্ষণ করি। এই সর্বনিম্ন ব্যবহার করে, আমরা $O(1)$-এ বর্তমান সর্বোত্তম ইনডেক্স $l$ খুঁজে পাই, এবং বর্তমান ইনডেক্স $r$ থেকে পরবর্তীতে যাওয়ার সময়, আমরা সহজভাবে এই সর্বনিম্ন আপডেট করি।

স্পষ্টতই, এই অ্যালগরিদম $O(n)$-এ কাজ করে এবং অ্যাসিম্পটোটিকভাবে সর্বোত্তম।

ইমপ্লিমেন্টেশন#

এটি ইমপ্লিমেন্ট করতে, আমাদের স্পষ্টভাবে আংশিক যোগফলের অ্যারে $s[]$ সংরক্ষণ করার প্রয়োজন নেই — আমাদের শুধু এর বর্তমান উপাদানটি প্রয়োজন হবে।

ইমপ্লিমেন্টেশনটি ০-ইনডেক্সড অ্যারেতে দেওয়া হয়েছে, উপরে বর্ণিত ১-নম্বরিং-এ নয়।

প্রথমে আমরা একটি সরল সংখ্যাসূচক উত্তর খুঁজে বের করার সমাধান দিই যেখানে কাঙ্ক্ষিত সেগমেন্টের ইনডেক্স খোঁজা হয় না:

int ans = a[0], sum = 0, min_sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum - min_sum);
    min_sum = min(min_sum, sum);
}

এখন আমরা সম্পূর্ণ সমাধান দিই, যেখানে অতিরিক্তভাবে কাঙ্ক্ষিত সেগমেন্টের সীমানাও খুঁজে বের করা হয়:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, min_sum = 0, min_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    int cur = sum - min_sum;
    if (cur > ans) {
        ans = cur;
        ans_l = min_pos + 1;
        ans_r = r;
    }
    if (sum < min_sum) {
        min_sum = sum;
        min_pos = r;
    }
}

অ্যালগরিদম ২#

এখানে আমরা একটি ভিন্ন অ্যালগরিদম বিবেচনা করি। এটি বুঝতে একটু বেশি কঠিন, কিন্তু এটি উপরেরটির চেয়ে বেশি মার্জিত, এবং এর ইমপ্লিমেন্টেশন একটু ছোট। এই অ্যালগরিদমটি জে কাডেন ১৯৮৪ সালে প্রস্তাব করেছিলেন।

অ্যালগরিদমের বর্ণনা#

অ্যালগরিদমটি নিম্নরূপ। আমরা অ্যারের মধ্য দিয়ে যাই এবং কোনো একটি চলক $s$-এ বর্তমান আংশিক যোগফল জমা করি। যদি কোনো সময়ে $s$ ঋণাত্মক হয়, আমরা কেবল $s=0$ নির্ধারণ করি। দাবি করা হয় যে অ্যালগরিদম চলাকালীন $s$ চলকে নির্ধারিত সমস্ত মানের মধ্যে সর্বাধিকটি হবে সমস্যার উত্তর।

প্রমাণ:

প্রথম যে ইনডেক্সে $s$-এর যোগফল ঋণাত্মক হয় তা বিবেচনা করুন। এর অর্থ হলো শূন্য আংশিক যোগফল দিয়ে শুরু করে, আমরা শেষ পর্যন্ত একটি ঋণাত্মক আংশিক যোগফল পাই — তাই অ্যারের এই সম্পূর্ণ প্রিফিক্স, সেইসাথে এর যেকোনো সাফিক্সের যোগফল ঋণাত্মক। অতএব, এই সাবঅ্যারেটি কখনোই এমন কোনো সাবঅ্যারের আংশিক যোগফলে অবদান রাখে না যার এটি প্রিফিক্স, এবং এটি সরলভাবে বাদ দেওয়া যায়।

তবে, অ্যালগরিদমটি প্রমাণ করতে এটি যথেষ্ট নয়। অ্যালগরিদমে, আমরা আসলে শুধুমাত্র সেই সেগমেন্টগুলোতে উত্তর খুঁজতে সীমাবদ্ধ যেগুলো $s<0$ ঘটার ঠিক পরের স্থান থেকে শুরু হয়।

কিন্তু, প্রকৃতপক্ষে, একটি ইচ্ছামতো সেগমেন্ট $[l, r]$ বিবেচনা করুন, এবং $l$ এমন একটি “ক্রিটিক্যাল” অবস্থানে নেই (অর্থাৎ $l > p+1$, যেখানে $p$ হলো শেষ এমন অবস্থান, যেখানে $s<0$ হয়েছিল)। যেহেতু শেষ ক্রিটিক্যাল অবস্থান $l-1$-এর কঠোরভাবে আগে, তাই দেখা যাচ্ছে যে $a[p+1 \ldots l-1]$-এর যোগফল অঋণাত্মক। এর মানে হলো $l$-কে $p+1$ অবস্থানে সরালে, আমরা উত্তর বাড়াব অথবা, চরম ক্ষেত্রে, এটি অপরিবর্তিত থাকবে।

যেভাবেই হোক, দেখা যাচ্ছে যে উত্তর অনুসন্ধানের সময়, আমরা কেবল সেই সেগমেন্টগুলোতে নিজেদের সীমাবদ্ধ রাখতে পারি যেগুলো $s<0$ দেখা দেওয়ার ঠিক পরের অবস্থান থেকে শুরু হয়। এটি প্রমাণ করে যে অ্যালগরিদমটি সঠিক।

ইমপ্লিমেন্টেশন#

অ্যালগরিদম ১-এর মতো, প্রথমে আমরা একটি সরলীকৃত ইমপ্লিমেন্টেশন দিই যেটি কাঙ্ক্ষিত সেগমেন্টের সীমানা না খুঁজে শুধু সংখ্যাসূচক উত্তর বের করে:

int ans = a[0], sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum);
    sum = max(sum, 0);
}

একটি সম্পূর্ণ সমাধান, সংশ্লিষ্ট সেগমেন্টের সীমানার ইনডেক্সও রক্ষণাবেক্ষণ করে:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}