最大子段和
題目描述
給出一個長度為 n n n 的序列 a a a，選出其中連續(xù)且非空的一段使得這段和最大。
輸入格式
第一行是一個整數(shù)，表示序列的長度 n n n。
第二行有 n n n 個整數(shù)，第 i i i 個整數(shù)表示序列的第 i i i 個數(shù)字 a i a_i ai?。
輸出格式
輸出一行一個整數(shù)表示答案。
樣例
樣例輸入
7
2 -4 3 -1 2 -4 3
樣例輸出
4
提示
樣例 1 解釋
選取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , ? 1 , 2 } \{3, -1, 2\} {3,?1,2}，其和為 4 4 4。
數(shù)據(jù)規(guī)模與約定
- 對于 40 % 40\% 40% 的數(shù)據(jù)，保證 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。
- 對于 100 % 100\% 100% 的數(shù)據(jù)，保證 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105， ? 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 ?104≤ai?≤104。
基本方法
當解決最大連續(xù)子序列和問題時，可以使用兩種基本方法：暴力法和動態(tài)規(guī)劃法。
純暴力
暴力法是最直觀的解決方法，它通過遍歷所有可能的子序列，并計算它們的和，最后返回最大的和。具體步驟如下：
初始化一個變量
m
a
x
x
maxx
maxx為負無窮大，用于記錄最大和。
使用兩個嵌套循環(huán)遍歷所有可能的子序列起點和終點。
在內(nèi)層循環(huán)中，計算當前子序列的和，并將其與
m
a
x
x
maxx
maxx進行比較，更新
m
a
x
x
maxx
maxx。
最后返回
m
a
x
x
maxx
maxx作為結(jié)果。
例如，對于序列
[
?
2
,
1
,
?
3
,
4
,
?
1
,
2
,
1
,
?
5
,
4
]
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
[?2,1,?3,4,?1,2,1,?5,4]，暴力法將遍歷所有可能的子序列，計算它們的和，并返回最大的和，即
6
6
6，對應(yīng)子序列
[
4
,
?
1
,
2
,
1
]
[4, -1, 2, 1]
[4,?1,2,1]。
暴力法的時間復(fù)雜度為 O ( n 2 ) O(n^2) O(n2)，其中 n n n是序列的長度。
動態(tài)規(guī)劃法
動態(tài)規(guī)劃法是一種更高效的解決方法，它通過利用子問題的最優(yōu)解來構(gòu)建整個問題的最優(yōu)解。具體步驟如下：
初始化兩個變量
m
a
x
x
maxx
maxx和
l
l
ll
ll，分別用于記錄全局最大和和當前子序列的和。
遍歷整個序列，對于每個元素，將其與
l
l
ll
ll相加，如果結(jié)果大于當前元素本身，則更新
l
l
ll
ll為相加結(jié)果；否則，將
l
l
ll
ll更新為當前元素。
在每次更新
l
l
ll
ll時，將其與
m
a
x
x
maxx
maxx進行比較，如果
l
l
ll
ll大于
m
a
x
x
maxx
maxx，則更新
m
a
x
x
maxx
maxx為
l
l
ll
ll。
最后返回
m
a
x
x
maxx
maxx作為結(jié)果。
例如，對于序列
[
?
2
,
1
,
?
3
,
4
,
?
1
,
2
,
1
,
?
5
,
4
]
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
[?2,1,?3,4,?1,2,1,?5,4]，動態(tài)規(guī)劃法將遍歷整個序列，計算當前子序列的和，并更新
m
a
x
x
maxx
maxx和
l
l
ll
ll。最終，返回
m
a
x
x
maxx
maxx的值為
6
6
6，對應(yīng)子序列
[
4
,
?
1
,
2
,
1
]
[4, -1, 2, 1]
[4,?1,2,1]。
動態(tài)規(guī)劃法的時間復(fù)雜度為 O ( n ) O(n) O(n)，其中 n n n是序列的長度。文章來源：http://www.zghlxwxcb.cn/news/detail-769881.html
總結(jié)： 暴力法是一種簡單直觀的解決方法，但在處理大規(guī)模序列時效率較低。動態(tài)規(guī)劃法通過利用子問題的最優(yōu)解，將問題分解為更小的子問題，從而提高了效率。在實際應(yīng)用中，動態(tài)規(guī)劃法是解決最大連續(xù)子序列和問題的常用方法。文章來源地址http://www.zghlxwxcb.cn/news/detail-769881.html
A C 代碼
#include <bits/stdc++.h>
using namespace std;
long long n,a,ll,maxx;
int main() {
cin >>n >>a;
ll=a; maxx=a;
for (int i=2;i<=n;i++)
{
cin >>a;
if (ll+a<0)
ll=0;
else
{
ll+=a;
maxx=max(maxx,ll);
}
}
cout <<maxx;
return 0;
}
到了這里，關(guān)于【動態(tài)規(guī)劃基礎(chǔ)】求最大連續(xù)子序列和——最大子段和的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
