ম্যাক্সিমাম সাব অ্যারে সাম – পর্ব ১

এখানে একটি n সংখ্যক উপাদানের অ্যারে  দেয়া থাকবে। এখান থেকে সাম্ভাব্য সবচেয়ে বড় a sequence of consecutive (পরপর) সাব অ্যারের উপাদানের সাম(Sum) বের করতে হবে। প্রবলেমটা আরো ইন্টারেস্টিং হবে যদি অ্যারেতে ঋণাত্মক মান থাকে। প্রবলেমটা তিন ভাবে সলভ করা যায়।

  • O(n³)
  • O(n²)
  • O(n)

মনে করি আমাদের একটি অ্যারে আছে int[ ] array = {-1, 2, 4, -3, 5, 2, -5, 2}। সোজাসাপ্টা Solution হল লুপ চালিয়ে all possible subarray এর সাম বের করা এবং ম্যাক্সিমামটা নেয়া।

using System;
namespace cSharp
{
class Program
{
static void Main(string[] args)
{
int[] arr = {-1, 2, 4, -3, 5, 2, -5, 2};
int maxNum = 0;
int length = arr.Length;

for(int i = 0; i<length; i++) {
    for(int j = i; j<length; j++) {
      int sum = 0;
       for(int k = i; k<=j; k++) {
       sum+=arr[k];
       }
     maxNum = Math.Max(maxNum,sum);
     }
   }
   Console.WriteLine(maxNum);
  }
 }
}

এখানে i এবং j ভ্যারিয়েবেল সাব অ্যারে  এর প্রথম এবং শেষ index ফিক্স করতে ব্যবহার করা হয়েছে।

এইটার টাইম কমপ্লিক্সিটি O(n³) কারন তিনটা লুপ ব্যবহার করা হয়েছে। O(n²) এর সলিউশন চিন্তা করুন। পরবর্তী অংশে বলা হবে।

Source: Competitive Programmer’s Handbook By Antti Laaksonen

ফেসবুক এ শেয়ার করুন

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *