সমস্যা বিবরণ
একটি ধনাত্মক ও ঋণাত্মক পূর্ণসংখ্যার অ্যারে দেওয়া আছে। ঐ অ্যারেতে সর্বোচ্চ সাবঅ্যারে যোগফল বের করতে হবে।
উদাহরণ
ইনপুট অ্যারে হলে {-12, -5, 4, -1, -7, 1, 8, -3} আউটপুট হবে 9।
এলগরিদম
- ইনপুট অ্যারের প্রিফিক্স সাম গণনা করুন।
- ইনিশিয়ালাইজ করুন:
min_prefix_sum = 0,res = -infinity। i = 0থেকেn-1পর্যন্ত লুপ চালান (n = অ্যারের আকার)।cand = prefix_sum[i] - min_prefix_sum- যদি cand বর্তমান
res-এর চেয়ে বড় হয়, তবেres-কেcandদিয়ে আপডেট করুন। - যদি
prefix_sum[i]বর্তমানmin_prefix_sum-এর চেয়ে ছোট হয়, তবেmin_prefix_sum-কেprefix_sum[i]দিয়ে আপডেট করুন। resরিটার্ন করুন।
C++ কোড উদাহরণ
#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
