بیشترین زیرآرایه
Maximum SubarrayMaximum Subarray به‌دنبال یک بخش پیوسته با بیشترین مجموع است و الگوریتم Kadane آن را در O(n) حل می‌کند.
اول این مفهوم را در ذهن نگه دار
Maximum Subarray به‌دنبال یک بخش پیوسته با بیشترین مجموع است و الگوریتم Kadane آن را در O(n) حل می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
در هر موقعیت تصمیم می‌گیریم segment قبلی را ادامه دهیم یا از مقدار فعلی یک segment جدید شروع کنیم.
هم best ending here و هم best global را نگه می‌داریم.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
State را دقیق تعریف کن.
Transition یا choice را از stateهای کوچک‌تر بنویس.
Base Case را مشخص و بعد بین memoization، tabulation یا backtracking انتخاب کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای بیشترین زیرآرایه هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function maxSubarray(a) {
let ending = a[0];
let best = a[0];
for (let i = 1; i < a.length; i++) {
ending = Math.max(a[i], ending + a[i]);
best = Math.max(best, ending);
}
return best;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n) with Kadane
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی زیرمسئله‌ها overlap دارند و جواب از stateهای کوچک‌تر ساخته می‌شود DP مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف state سراغ recurrence نرو.
- DPای نساز که state space آن از خود مسئله بزرگ‌تر و غیرعملی باشد.
مدل یک پاسخ حرفه‌ای
منطق تصمیم محلی Kadane را توضیح بده و حالت همه اعداد منفی را درست هندل کن؛ مقدار اولیه صفر می‌تواند آن حالت را خراب کند.
بیشترین زیرآرایه چه مسئله‌ای را حل می‌کند؟
Maximum Subarray به‌دنبال یک بخش پیوسته با بیشترین مجموع است و الگوریتم Kadane آن را در O(n) حل می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n) with Kadane است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف state سراغ recurrence نرو.