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) কম্বিনেশন এর জন্য কাজ করলেই আমরা আমাদের মূল রেজাল্ট পেয়ে যাবো। 

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

Happy Coding