题解 | 最大子段和

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//设dp[n]为以第n个元素为结尾能够取到的最大子段和 对于dp[n] 我们假设已经知道dp[n-1]的大小 然后我们只需要知道 dp[n-1]加上第n个元素和第n个元素本身谁大即可 从而得出dp[n]
    ll n,MAX=-2e10;
    cin >> n;
    vector<ll>v(n+1,0),dp(n+1,0);
    for(int i=1;i<=n;i++) cin >> v[i];
    dp[1]=v[1];
    for(int i=2;i<=n;i++)
    {
        dp[i]=max(v[i],v[i]+dp[i-1]);//状态转移方程
        MAX=max(MAX,dp[i]);//记得存储最大值
    }
    cout << MAX;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}