یکی از مسئلههای معروف الگوریتم و روش استقرایی، این مسٔله میباشد. در زیر به بررسی این مسٔله و روش حل دقیق آن میپردازیم.
فرض کنید یک آرایهی 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)$ است.
#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; }