PTA1007 Maximum Subsequence Sum(最大连续子串的和,dp)

分析：dp问题，状态转移方程：$dp[i]=max(dp[i?1]+a[i],dp[i])$,其中dp[i]表示以i结尾的最大连续字串和。

#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
int a[11000],dp[11000];
bool flag=false;
int n,s,e,sta,edd,maxx;
int main(){
    std::ios::sync_with_stdio(false);cin>>n;for(int i=0;i<n;i++){
    cin>>a[i];//注意，这里是>=0if(a[i]>=0){
    flag=true;}}if(!flag) {
    cout<<"0"<<" "<<a[0]<<" "<<a[n-1]<<endl;return 0;}s=e=sta=edd=0;maxx=dp[0]=a[0];for(int i=1;i<n;i++){
    if(a[i]>dp[i-1]+a[i]){
    dp[i]=a[i];s=e=i;}else{
    dp[i]=dp[i-1]+a[i];e=i;}if(maxx<dp[i]){
    maxx=dp[i];sta=s;edd=e;}}cout<<maxx<<" "<<a[sta]<<" "<<a[edd]<<endl;return 0;
}