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

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

فرض کنید یک آرایه‌ی 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)$ است.

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;
}