সমস্যা বিবৃতি
ধনাত্মক এবং নেতিবাচক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হলে, সেই অ্যারেতে সর্বাধিক সুবারে যোগফল বের করুন
উদাহরণ
যদি ইনপুট অ্যারে হয় − {-12, -5, 4, -1, -7, 1, 8, -3} তাহলে আউটপুট 9
অ্যালগরিদম
-
ইনপুট অ্যারের উপসর্গ যোগফল গণনা করুন।
-
ইনিশিয়ালাইজ করুন− min_prefix_sum =0, res =-infinite
-
i =0 থেকে n এর জন্য একটি লুপ বজায় রাখুন। (n হল ইনপুট অ্যারের আকার)।
-
cand =prefix_sum[i] – mini
-
যদি ক্যান্ড res এর থেকে বড় (এখন পর্যন্ত সর্বাধিক সাবয়ারের যোগফল), তারপর ক্যান্ড দ্বারা res আপডেট করুন।
-
যদি উপসর্গ_সাম[i] min_prefix_sum (এখন পর্যন্ত ন্যূনতম উপসর্গ যোগফল) থেকে কম হয়, তাহলে উপসর্গ_সম[i] দ্বারা মিন_প্রেফিক্স_সম আপডেট করুন।
-
-
রিটার্ন রিটার্ন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
int minPrefixSum = 0;
int res = numeric_limits<int>::min();
int prefixSum[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
for (int i = 0; i < n; i++) {
res = max(res, prefixSum[i] - minPrefixSum);
minPrefixSum = min(minPrefixSum, prefixSum[i]);
}
return res;
}
int main(){
int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
return 0;
} আউটপুট
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি অনুসরণ করে আউটপুট −
তৈরি করেResult = 9
