@میتراتالوریمیترا تالوری
حل مشکلات کوچکتر امروز برای حل مشکلات بزرگتر فردا!
با توجه به یک آرایه ، الگوریتم پیدا کردن حداکثر مجموع زیرآرایه را الگوریتم Kadane می نامند.
آرایه می تواند از هر بعدی باشد. برای سادگی ، بیایید با یک آرایه 1D شروع کنیم.
بیایید یک آرایه 0-index کنیم:
arr: [5, 7, -3, 2, 9, 6, 16, 22, 21, 29, -14, 10, 12]
ما می توانیم زیر مجموعه را در هر نقطه شروع کنیم. بیایید بگوییم ما از شاخص 2 یعنی arr شروع می کنیم[2] = -3
اکنون ، در شاخص 3 ، مجموع -3 + 2 = -1 خواهد بود.
اگر در عوض زیرشاخه را با شاخص 3 شروع کنیم ، جمع در شاخص 3 برابر 2 است که بیشتر از جمع قبلی است.
بنابراین ما دو گزینه داریم: یا از شاخص فعلی شروع کنید یا عنصر فعلی را به جمع قبلی اضافه کنید.
و از آنجا که ما حداکثر مجموع زیر مجموعه را می خواهیم ، عنصر فعلی را به حداکثر 0 و مجموع قبلی اضافه می کنیم (صفر در اینجا نشان می دهد که ما از عنصر فعلی از نو شروع می کنیم).
این مشکل تحت پارادایم برنامه نویسی پویا قرار می گیرد
بیایید یک آرایه DP بگیریم[] جایی که هر dp[i] حداکثر مجموع زیر مجموعه را با پایان دادن به شاخص i نشان می دهد (از جمله i).
می توان گفت که:
شرایط پایه:
dp[0] = عقب[0]
پاسخ:
حداکثر عنصر در dp[] آرایه
پیچیدگی زمان: بر)
پیچیدگی فضا: بر)
با استفاده از dp می توانیم پیچیدگی فضا را بهینه کنیم[i-1] که حاصل جمع قبلی به یک متغیر است ، حذف …