اَلگونَوَردی ۱: زیر آرایه با مجموع ماکزیمم را بیابید (حل شد توسط Iman)

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

قانون اول الگونوردی: با ترس خود رودر رو شوید!

گروه الگونوردی قوانینی دارد. قانون اول الگونوردی آن است که باید با ترس خود رودر رو شوید. آدمی از نقطه ضعف هایش می ترسد. الگو نوردان انسانهای با شهامتی هستند. بجای اینکه بگذارند که یک تکنیک الگوریتمی آنها را از پادرآورد، در تمرینات خود روی نقطه ضعف خود تمرکز می کنند. آنقدر تمرین می کنند که نقطه ضعفشان به نقطه قوتشان تبدیل شود.

بله، مثلا داینامیک پروگرمینگ خودمان بر بدن خیلی ها لرزه می اندازه. این هفته می خواهیم با این ترس رو برو شویم و تمرین کنیم تا اندکی خود را قوی تر کنیم. این هفته را خوب دوام بیاورید. قول می دهم دیگر از داینامیک پروگرمینگ یا هیچ مساله دیگری نترسید!

دسترسی و حل سوال از منبع اصلی

پرسش: یک آرایه از اعداد صحیح داده شده است. برنامه ای بنویسید که زیر آرایه پیوسته ای (با حداقل یک عنصر) که مجموع مقادیرش (sum) ماکزیمم هست را بیابد و sum را برگرداند.

مثال: اگر لیست [1, 1-, 2-, 5, 7-, 2] داده شود، باید مقدار 5 را برگرداند. زیر آرایه [5] ماکزیمم است.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۸۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز ۳۰ مارچ

یادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.

توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.

حل مساله

الگونورد برتر: الگونورد برتر الگونورد 1، کاربر با ای دی Iman هست.

ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. تشریح حل مساله رو من در نقاطی ویرایش و ساده سازی کردم.

به Iman تبریک می گم و بهش می گم: خیلی خوبی! ادامه بده!

و حالا شرح پاسخ:

حل مسئله را با یک مثال ساده شروع می‌کنیم تا مطمئن شویم که مسئله را به خوبی متوجه شده‌ایم. فرض کنید یک آرایه حاوی 4 عضو داریم به صورت زیر:

A=[3, -2, 5, -1]

می خواهیم مجموع زیر آرایه به هم پیوسته از آرایه A را بیابیم به گونه‌ای که مجموع عناصر آن از مجموع مرتبط با سایر زیر آرایه‌ها بیشتر باشد (مقدار ماکزیمم). شروع زیر آرایه می‌تواند از هر یک از اندیس های 0 تا n-1 و انتهای آن نیز مربوط به هریک از عناصر بعد آن در آرایه باشد. بنابراین تعداد کل این زیرآرایه‌های پیوسته برابر با n*(n+1)/2  که در آن n تعداد عناصر آرایه هست. به عنوان مثال، تعداد 10 زیرآرایه‌ پیوسته برای A  وجود دارند که در زیر به همراه مجموع عناصر هر یک نشان داده شده اند:

[3]=>S[0]=3
[3,-2]=>S[1]=1
[3,-2, 5]=>S[2]=6
[3, -2, 5, -1]=>S[3]=5
[-2]=>S[4]=-2
[-2,5]=>S[5]=3
[-2,5,-1 ]=>S[6]=2
[5]=>S[7]=5
[5,-1 ] =>S[8]=4
[-1]=>S[9]=-1

ماکزیمم برابر 6 برای رشته [S[2 می‌باشد، که اندیس شروع عنصر اول آن برابرi=0 و اندیس عنصر پایانی آن  j=2 می‌باشد.

ارائه الگوریتم برای حل این مساله را از الگوریتم جستجوی کامل شروع می‌کنیم. روش‌ جستجوی کامل همه زیر آرایه‌های پیوسته ممکن را تشکیل می‌دهد. برای این کار می‌توانیم یک متغیر i برای حلقه بیرونی (جهت دسترسی به عناصر به ابتدای زیر آرایه) و یک متغیر j برای حلقه میانی (جهت انتخاب عنصر پایان زیر آرایه) و یک متغیر k برای حلقه داخلی جهت پیمایش عناصر زیر آرایه پیوسته از i تا j در نظر می گیریم. حاصل جمع عناصر زیر آرایه را در متغیر s می گذاریم. در واقع برای هر زیر آرایه، s مجموع تمام عناصر در زیر آرایه را در خود نگه می‌دارد. پس از محاسبه مجموع زیر آرایه اگر s بزرگتر از ماکزیممی باشد که تا بحال بدست آمده است، آن را جایگزین ماکزیمم کنونی می‌کنیم. به این دلیل که دو حلقه تکرار داریم و هر بار باید مجموع تمام عناصر زیر آرایه را محاسبه کنیم، مرتبه اجرایی الگوریتم (O(n^3خواهد بود.

مشکل این روش این است که در هر تکرار حلقه میانی، مجموع زیر آرایه جدید (یعنی از i تا j جدید) را با استفاده از حلقه داخلی، از نو شروع می کنیم. در حالی که زیر آرایه جدید تنها یک عنصر از زیر آرایه قبلی بیشتر دارد. بنابر این می توان با استفاده از مجموع زیر آرایه قبلی (یعنی i تا j-1 ) و افزودن مقدار عنصر j ام، مجموع زیر آرایه جدید یعنی از i تا j  را محاسبه نمود. به این ترتیب، عملا نیاز به حلقه داخلی نیست. در نتیجه مرتبه اجرایی الگوریتم جدید به (O(n^2 کاهش خواهد یافت. قطعه کد زیر پیاده سازی الگوریتم بهینه شده جستجوی کامل را نشان می دهد.

اشکال روش جستجوی کامل آن است که محاسبات اضافی انجام می دهد. متاسفانه نحوه فرمول کردن راه حل بصورت جستجوی کامل، غیر از بهینه سازی ای که ذکر شد، اجازه نمی دهد که نتایج بعدی را از روی نتایج قبلی بسازیم. برای یافتن روش بهتر، باید دیدگاه خاصی را در ذهن خود پرورش بدهیم که اجازه می دهد راه حل جدید را بدهد.

این نگاه خاص 'روش تفکر استقرایی' است.

در این مساله تفکر استقرایی به این معناست که:

اگر فرض کنیم که راه حل را برای یک آرایه i عنصری بدانیم، چگونه می توانیم راه حل را برای آرایه i+1 عنصری (ایجاد شده با افزودن یک عنصر به انتهای آرایه i عنصری) بیابیم؟

یک نگاه خاص تر استقرایی آن است که:

اگر فرض کنیم که زیرآرایه با مجموع ماکزیمم که به عنصر i ام ختم می شود را بدانیم، چگونه می توانیم زیرآرایه با مجموع ماکزیمم تا عنصرi+1 ام را محاسبه کنیم؟

به عبارت دقیق تر، اگر از روی آرایه اصلی A داده شده آرایه جدید L را بگونه ای بسازیم که عنصر i ام آن مجموع زیرآرایه‌ با مجموع ماکزیمم که به عنصر i ام ختم می شود را در خود ذخیره کند، آنگاه چگونه می توانیم مقدار عنصر i+1 ام را از روی عنصر i ام بیابیم؟

با فرض اینکه زیر آرایه با مجموع ماکزیمم خاتمه یافته به عنصر i ام را می دانیم (یعنی [L[i)، ممکن است دو حالت زیربرای Li+1 بوجود آید:

• مقدار [A[i+1از مجموع محاسبه شده تا عنصر i ام (یعنی [L[i) بزرگتر است. بنابر این [L[i+1برابر با [A[i+1خواهد بود.
• مقدار [A[i+1از مجموع محاسبه شده تا عنصر i ام کوچکتر است. بنابر این [L[i+1برابر با [L[i]+A[i+1خواهد بود.

  به عبارت دیگر، با در نظر گرفتم ]L[0]=A[0 , فرمول محاسبه مقدار زیر آرایه ماکزییم که بعنصر iام (i > 1) ختم می شود به این صورت است:

L[i+1]=max⁡(A[i+1], A[i+1]+L[i])

با اجرای استقرای گفته شده روی مثال آرایه A که در بالا داده شد، مقادیر زیر یکی بعد از دیگری محاسبه می شوند:

مقدار دهی اولیه:

[3]=>L[0]=3

و بر این اساس مقادیر بعدی به این صورت خواهند بود:

[3, -2]=>L[1]=max(-2,-2+3) =1
[3, -2, 5]=>L[2]=max(5,5+1) =6
[3, -2, 5, -1]=>L[3]=max(-1,-1+6) =5

پاسخ روش استقرایی با روش جستجوی کامل همخوانی دارد. با توجه به این که در این روش تنها یکبار لیست A را پیمایش می کنیم و هر بار مقدار ماکزیمم را محاسبه می کنیم، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.

بر این اساس، شروع به پیاده سازی الگوریتم می کنیم. به خاطر داشته باشید که در زمان مصاحبه، خطوط برنامه را بصورت همزمان برای مصاحبه کننده توضیح می دهیم. در سطر 1 تابع maxSubArray یک آرایه حاوی اعداد دریافت می‌کند.

در سطر 2 دو متغیر تعریف شده که متغیر local_max همان Li و متغیر global_max که ماکزیمم کل کنونی دا در خود نگه می دارد را مقدار دهی اولیه می کنیم. در سطر 3 یک حلقه از عنصر دوم آرایه تعریف شده است. در سطر 4 و 5 فرض استقراء تعریف شده است.

و در سطر 6 مقدار sum که همان بیشینه سراسری است، بازگشت داده شده است.

شاید برای شما شگفت آور باشد، اما به این سادگی اولین سوال برنامه نویسی پویا را حل کردید. تفکر استقرایی قلب برنامه نویسی پویاست. سعی کنید آن را در ذهن خوب بپرورانید.