আকার N এর একটি অ্যারে শূন্য দিয়ে ইনিশিয়ালাইজড। M সংখ্যক রেঞ্জ আপডেট অপারেশন update[L, R, K] (L থেকে R পর্যন্ত সব উপাদানে K যোগ করা) দেওয়া আছে। সব অপারেশন শেষে অ্যারেতে সর্বোচ্চ মান কত তা বের করতে হবে।
উদাহরণ
N = 6, M = 4
Updates = {{1,4,12}, {0,3,5}, {1,5,7}, {3,5,10}}
আউটপুট: 34
দুটি পদ্ধতি
১. নїв পদ্ধতি (O(M×N))
প্রতিটি অপারেশনে লুপ চালিয়ে আপডেট করুন।
২. অপ্টিমাইজড পদ্ধতি (O(M+N)) — ডিফারেন্স অ্যারে
- প্রতিটি
update[L,R,K]এর জন্য:arr[L] += K; arr[R+1] -= K; - শেষে প্রিফিক্স সম দিয়ে actuall array বানান এবং সর্বোচ্চ মান খুঁজুন।
C++ প্রোগ্রাম (অপ্টিমাইজড)
#include <iostream>
using namespace std;
int findMax(int arr[], int N) {
int maxVal = 0, sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[i];
maxVal = max(maxVal, sum);
}
return maxVal;
}
void updateVal(int arr[], int L, int R, int K) {
arr[L] += K;
arr[R+1] -= K;
}
int main() {
int N = 6;
int arr[N] = {0};
int M = 4;
int ops[M][3] = {{1,4,12}, {0,3,5}, {1,5,7}, {3,5,10}};
for (int i = 0; i < M; i++)
updateVal(arr, ops[i][0], ops[i][1], ops[i][2]);
cout << "Maximum value after " << M << " operations: " << findMax(arr, N);
return 0;
}
আউটপুট: Maximum value after 4 range increment operations is 34
