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

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

===== الگوریتم =====
برای حل این سؤال، آرایه‌ی $D$ را به این صورت تعریف میکنیم: \\
$D_i$ برابر است با مقدار بیشینه‌ی جمع زیر‌آرایه‌ای، که خانه‌انتهایی آن، $i$ باشد. \\
حال بیایید مقدار $D_i$ را به صورت استقرایی بیابیم.
$D_1 = A_1$
است. واضح است که به ازای خانه‌ی ابتدایی، تنها زیر‌آرایه‌ای که به این خانه منتهی می‌شود، زیر‌آرایه متشکل از خود این خانه است. حال به ازای هر
$i > 1$
خواهیم داشت:
$$D_i = max(A_i, A_i + D_{i-1})$$
زیرا یا زیر‌آرایه‌ی ختم شده به خانه‌ی $i$ام از خانه‌های قبلی استفاده‌ می‌کند، یا استفاده ‌نمی‌کند. که عبارت بالا، هر دوی این حالات را بررسی می‌کند. \\
اکنون که به ازای هر $i$، مقدار $D_i$ داریم، کافی است بیشترین مقدار $D_i$ ها را به دست بیاوریم، تا جواب سؤال را بیابیم.

===== پیچیدگی‌ الگوریتم =====
با توجه به الگوریتم استقرایی که ارائه شد، بسیار راحت می‌توان نشان داد که پیچیدگی این الگوریتم از 
$O(N)$
است.

===== پیاده‌سازی =====

<code cpp maximum_subarray.cpp>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000 * 1000; // maximum size of array
int A[maxn], D[maxn];
int main() {
    int N;
    cin >> N;
    for(int i=0;i<N;++i)
        cin >> A[i];
    
    D[0] = A[0]; //start of array is 0
    for(int i=1;i<N;++i)
        D[i] = max(D[i - 1] + A[i], A[i]);
    
    int ans = D[0];
    for(int i=1;i<N;++i)
        ans = max(ans, D[i]);
    
    cout << ans << endl;
}
</code>