Minimum Sub-Array Sum

Problem:

এই প্রব্লেমে আমাকে একটি অ্যারে দেয়া থাকবে। ঐ অ্যারের এমন একটি সাব-অ্যারে নির্বাচন করতে হবে যার সংখ্যাগুলোর যোগফল সর্বনিম্ন হয়। 

Solution:

Maximum Sub-Array Sum এই পর্বটি পড়ে থাকলে এই প্রব্লেম সলভ করা খুবই সহজ। কীভাবে?

১) অ্যারের প্রতিটি সংখ্যার সাথে -১ গুণ করবো। অর্থাৎ, পজিটিভ সংখ্যাগুলোকে নেগেটিভ বানাবো আর নেগেটিভ গুলোকে পজিটিভ। 

২) তারপর, পরিবর্তিত এই অ্যারের Maximum Sub-Array Sum ক্যালকুলেট করবো।

৩) প্রাপ্ত রেজাল্ট কে -১ দ্বারা গুণ করবো। কাজ শেষ 😛

	#include<bits/stdc++.h>
	#define ll long long
	using namespace std;
	ll ara[100009],prefsum[100009];
	int main()
	{
	ll n , mnSubAraSum = 0, mnTillNow = 0;
	cin>>n;
	for(ll i=1 ; i<=n ; i++){
	cin>>ara[i];
	ara[i] *= -1;
	prefsum[i] = prefsum[i-1] + ara[i];
	ll mnSubAraSumEndsHere = prefsum[i] - mnTillNow;
	mnSubAraSum = max(mnSubAraSum , mnSubAraSumEndsHere);
	mnTillNow = min(mnTillNow , prefsum[i]);
	cout<<mnSubAraSumEndsHere<<endl;
	}
	mnSubAraSum *= -1;
	cout<<mnSubAraSum<<endl;
	return 0;
	}

view raw MinimumSubArray.cpp hosted with ❤ by GitHub