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

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

static void Main(string[] args)
{
int[] array = {-1, 2, 4, -3, 5, 2, -5, 2};
int n = array.Length;
int best = 0;
for (int a = 0; a < n; a++) {
int sum = 0;
for (int b = a; b < n; b++) {
sum += array[b];
best = Math.Max(best,sum);
}
}
Console.WriteLine(best);
}

এখন আসি O(n) এর জন্য, যেহেতু Maximum বলা হয়েছে সেজন্য ঋণাত্মক উপাদান গুলো নিয়ে না ভেবে ধনাত্মক উপাদান গুলো দেখতে হবে।

        static void Main(string[] args)
        {
             int[] array = {-1, 2, 4, -3, 5, 2, -5, 2};
             int n = array.Length;
             int compareResult = int.MinValue; //MinValue-> public const int MinValue = -2147483648;
             int sum = 0;
             for(int i = 0; i<n; i++) {
                 sum = sum + array[i];
                 if(compareResult<sum){
                     compareResult = sum;
                 }
                 if(sum<0){
                     sum = 0;
                 }
             }
             Console.WriteLine(compareResult);
           
        }

এখানে compareResult ভেরিয়েবলে সর্বনিম্ন মান রাখা হয়েছে। তারপর sum এর সাথে compare করে Max Value টি
compareResult এ রাখা হয়েছে।

ভাল ভাবে বুঝাতে পারিনি। ক্ষমার দৃষ্টিতে দেখবেন।

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

You may also like...

Leave a Reply

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