Maximum Sum Rectangle in a 2D array

Problem:

এই প্রব্লেমে মূলত আমাকে 100 x 100 সাইজের একটি 2D অ্যারে দেয়া থাকবে। আমাকে ঐ অ্যারে তে এমন একটি আয়ত (Rectangle) নির্বাচন করতে হবে যাতে তার সংখ্যাগুলোর যোগফল সর্বোচ্চ হয়। যেমনঃ

উপরোক্ত 3 x 5 সাইজের 2D অ্যারের জন্য সম্ভাব্য সকল আয়তের মধ্যে সবুজ চিহ্নিত আয়তের সংখ্যাগুলোর যোগফল সর্বোচ্চ। 

Solution:

1D অ্যারে তে Maximum Sub-Array Sum বের করতে পারলে এই প্রব্লেমটি O(n^3) কমপ্লেক্সিটি তে সলভ করা সম্ভব। 

আমরা একটি আয়ত নির্বাচন এর জন্য তার Upper & Lower Row দুইটি ফিক্স করবো। এরপর, নতুন একটি অ্যারে তৈরী করবো। ঐ অ্যারের i'th Element হবে i'th Column বরাবর Upper Row to Lower Row এর সংখ্যাগুলোর যোগফল। এখন, এই নতুন অ্যারের Maximum Sub-Array Sum বের করে এন্সার কে ম্যাক্সিমাইজ করার চেষ্টা করবো। এভাবে, সম্ভাব্য সকল (Upper Row, Lower Row) = (i , j) কম্বিনেশন এর জন্য কাজ করলেই আমরা আমাদের মূল রেজাল্ট পেয়ে যাবো। 

কোডটি দেখতে যেমন হবেঃ 

	#include<bits/stdc++.h>
	#define ll long long
	using namespace std;
	#define sz 105
	ll mat[sz][sz],prefCol[sz][sz],ara[sz],prefsum[sz]; ///prefCol[i][j] = mat[1][i]+mat[2][i]+---+mat[j][i]
	///That means first j element's sum in column i
	int main()
	{
	ll row,col,mxSubRecSum=0;
	cin>>row>>col;
	for(ll i=1 ; i<=row ; i++){
	for(ll j=1 ; j<=col ; j++)
	cin>>mat[i][j];
	}
	for(ll i=1 ; i<=col ; i++){
	for(ll j=1 ; j<=row ; j++)
	prefCol[i][j] = prefCol[i][j-1] + mat[j][i];
	}
	for(ll pos1=1 ; pos1<=row ; pos1++){
	for(ll pos2=pos1 ; pos2<=row ; pos2++){
	ll mnTillNow = 0;
	for(ll j=1 ; j<=col ; j++){
	ara[j] = prefCol[j][pos2] - prefCol[j][pos1-1];
	prefsum[j] = prefsum[j-1]+ara[j];
	ll mxSubAraSumEndsHere = prefsum[j] - mnTillNow;
	mxSubRecSum = max(mxSubRecSum , mxSubAraSumEndsHere);
	mnTillNow = min(mnTillNow , prefsum[j]);
	}
	}
	}
	cout<<mxSubRecSum<<endl;
	return 0;
	}

view raw Max Sub Rectangle Sum.cpp hosted with ❤ by GitHub

Happy Coding