Maximum Sub-Array Sum

Problem:

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

Solution:

এটি খুবই কমন একটি প্রব্লেম যার অনেকগুলো সমাধান সম্ভব। তাই বিস্তারিত না বলে সরাসরি কোডে যাচ্ছি। আশা করি কোড দেখেই বুঝতে পারবেঃ 

	#include<bits/stdc++.h>
	#define ll long long
	using namespace std;
	ll ara[100009],prefsum[100009];
	int main()
	{
	ll n , mxSubAraSum = 0 , minTillNow = 0;
	///IF it is necessary to take at least one element then mxSubAraSum will be -1e18
	cin>>n;
	for(ll i=1 ; i<=n ; i++){
	cin>>ara[i];
	prefsum[i] = prefsum[i-1]+ara[i];
	ll mxSubAraSumEndsHere = prefsum[i] - minTillNow;
	mxSubAraSum = max(mxSubAraSum , mxSubAraSumEndsHere);
	minTillNow = min(minTillNow , prefsum[i]);
	}
	cout<<mxSubAraSum<<endl;
	return 0;
	}

view raw MaxSubArray.cpp hosted with ❤ by GitHub