本蒟蒻在练习DP中~
所以开个博客记录dp的题解~
欢迎关注~也欢迎各路julao吐槽代码qwq
难度什么的我刷到一定量的时候再打上
题面请点蓝色的字~
为了方便食用我就不贴头文件了（逃
DP介绍
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。利用各个阶段之间的关系，逐个求解，最终求得全局最优解，需要确认原问题与子问题、动态规划状态、边界状态、边界状态结值、状态转移方程。
T1：
最大子段和
分析：
这道题的子问题是什么，我们怎么刻画这件事？首先，把子问题看作求 前i个数中的最大子段和 是不可以的，因为这个描述并不足以刻画“连续”这一点，比如说，你求出了前5个数最大子段和是114，但是这个子段和却是由第2,3,4个数组成的，那么刻画5+1时候的方程就会出现不妥（即dp[i+1]无法刻画）。
因此，dp[i]应该被描述成子段带有第i个元素（或全部都不取（也就是0））的子段最大值，这样就可以描述“连续”这件事了。
据此，dp方程如下：
dp[i]=max(max(0,a[i]),dp[i-1]+a[i]);下面贴出代码：
int a[maxn];
int dp[maxn];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];if(*max_element(a+1,a+n+1)<0){cout<<*max_element(a+1,a+n+1); return 0;}//特判，这里很重要！！！要是全部是负数不可以输出0（因为子段非空）for(int i=1;i<=n;i++)dp[i]=max(max(0,a[i]),dp[i-1]+a[i]);int ans=*max_element(dp+1,dp+n+1); cout<<ans<<endl;return 0;
}