NYOJ 44 ---子串和

点击打开链接NYOJ44

题目: 子串和

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <stack>#include <queue>#include <cmath>#include <set>using namespace std;#define MAXN 1000010int t , n;int num[MAXN];int dp[2];void solve() { int max = -999999999; memset(dp , 0 , sizeof(dp)); dp[0] = num[0]; for(int i = 1 ; i < n ; i++){ if(dp[(i-1)%2]+num[i] > 0) dp[i%2] = dp[(i-1)%2]+num[i]; else dp[i%2] = 0; if(max < dp[i%2]) max = dp[i%2]; } printf("%d\n" , max);}int main() { //freopen("input.txt" , "r" , stdin); int max = -999999999; scanf("%d*c" , &t); while(t--){ scanf("%d*c" , &n); for(int i = 0 ; i < n ; i++){ scanf("%d" , &num[i]); if(max < num[i]) max = num[i]; } if(max > 0) solve(); else printf("%d\n" , max); } return 0;}