ZJ d784: 一、連續元素的和

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=d784

DP求最優解

dp[i]=max(dp[i-1]+input,input)

要特殊處理全部都是負數的情況

以下為code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int main()

{

AC

ll num;

cin>>num;

while(num--)

{

ll n,temp=-1e9;

bool worst=true;

cin>>n;

vector<ll> dp(n+1,0);

for(ll i=1;i<=n;i++)

{

ll t;

cin>>t;

if(t>0) worst=false;

dp[i]=max(t,dp[i-1]+t);

temp=max(t,temp);

}

if(worst) cout<<temp<<'\n';

else cout<<*max_element(dp.begin(),dp.end())<<'\n';

}

}