زیر‌آرایه با بیشینه‌ی جمع

یکی از مسئله‌های معروف الگوریتم و روش استقرایی، این مسٔله می‌باشد. در زیر به بررسی این مسٔله و روش حل دقیق آن می‌پردازیم.

فرض کنید یک آرایه‌ی N عضوی شامل اعداد $A_1,A_2,...,A_N$ داریم به طوری که حداقل یکی از این اعداد مثبت باشد. می‌خواهیم $i,j$ را طوری انتخاب کنیم که حاصل جمع اعداد این بازه، بیشترین مقدار ممکن شود. یعنی مقدار: $$\sum_{k=i}^{j}A_k$$ بیشترین مقدار خود را داشته باشد.

فرض کنید طول آرایه شما زوج است، برای طول‌های فرد نیز به طور مشابه، پرسش قابل حل است. ابتدا آرایه را به دو قسمت مساوی تقسیم کنید. اکنون برای دو قسمتی که دارید، سؤال را حل کنید. حال یا زیرآرایه با بیشینه جمع، در نیمه‌ی اول آرایه است، یا در نیمه‌ی دوم است، یا تعدادی از عناصر آن در نیمه‌ی اول و تعدادی در نیمه‌ی دوم هستند. اکنون اگر دو حالت اول اتفاق افتاده باشد، که سوال حل شده است و ما توانستیم با تقسیم کردن مسئله، به دو زیر مسئله‌ی دیگر، سؤال را حل کنیم. اگر حالت سوم اتفاق افتاده باشد، فرض کنید بیشینه‌ی جمعی که به عنصر $\frac{n}{2}$ ختم می‌شود برابر با $x$ و بیشینه‌ی جمعی که از عنصر $\frac{n}{2} + 1$ شروع می‌شود برابر $y$ باشد. واضح است که جواب نهایی برابر است با: $$x + y$$ جال اگر به ازای هر زیر مسئله، این بیشینه جمع‌ها را نیز نگه داریم، سؤال به راحتی قابل حل است.

از طریق روابط ریاضی که در زیر نوشته شده‌است می‌توان پیچیدگی الگوریتم را به راحتی تحلیل کرد: $$f(n) = 2f(n / 2) + O(1)$$ $$f(n) = O(n)$$ برای تحلیل دقیق این رابطه، می‌توانید از استقرا کمک بگیرید.