Longest Sub-Array with Sum K

Longest Sub-Array with Sum K 

সহজ প্রবলেম ডেসক্রিপশন,
একটা N সাইজের Array দেয়া থাকবে, একই সাথে একটা টার্গেট Sum দেয়া থাকবে, Array থেকে এমন একটা Subarray বের করতে হবে যার Length হবে ম্যাক্সিমাম. উল্লেখ্যঃ Array তে Negative Number ও থাকতে পারে.

Example:
Array[] = {5, 6, -5, 5, 3, 5, -2, 0}, target sum =  8

All Possible subarray With Sum 8:

{-5, 5, 3, 5}
{3, 5}
{5, 3}

এইখানে সব থেকে বড় সাইজের Subarray হচ্ছে {-5, 5, 3, 5},
যার সাইজ 4. অর্থাৎ এটাই আমাদের কাঙ্ক্ষিত Answer.


Bruteforce Solution:

সহজ ভাবে বলতে গেলে প্রত্যেকবার লুপ চালিয়ে একটা Subarray বের করতে হবে যেটার Sum হবে Target Sum এর সমান।
তাহলে প্রথম কাজ হচ্ছে Subarray Generate করা। দুইটা লুপ চালায়ে আমরা এই কাজ টা করতে পারি। 


Pseudo Code:

        for i = 0 to n-1
              for j = i to n-1
                sum+=a[i]
                 if(sum == target_sum)
                        maximum of (j-i+1)

এক্ষেত্রে Time Complexity হবে  O(n2).


Optimization:

উদাহরনে দেয়া Array টার কথা চিন্তা করি,

Index 0, 1, 2, 3,  4 , 5, 6
 Array 5, 6, -5, 5, 3, -2, 0

Array র শুরু থেকে প্রত্যেকবার Sum করতে করতে সামনে আগাইতে থাকবো, এবং এই Sum কে Index সহ মার্ক করে রাখবো, যেনো পরবর্তীতে এটা ইউজ করতে পারি.


অর্থ্যাত Prefix sum কাজে লাগবে এইখানে, আর মার্ক করে রাখার জন্য আমরা Map ব্যবহার করতে পারি.

তাহলে , প্রত্যেকবার যখন Sum পাবো, তখন Map এ চেইক করে দেখবো, আগে থেকেই Current Sum , Map এ আছে কিনা ! এর পর যখন দেখবো Current Sum - Target sum এর আগে অল্রেডি দেখে আসছি, অর্থ্যাত Map এ রাখা আছে, তারমানে Current Index থেকে Previous (Current Sum - Target sum) যেই Index এ দেখে আসছি এই Subarray টার যোগফল Target Sum.আর এই Subarray  র সাইজকে ম্যাক্সিমাম করতে হবে.

Code