最大子段和问题

P1115 最大子段和

思路：经典线性DP，dp[i]表示前i个元素的最大子段和， 最后输出max(ma, dp[i])即可

void solve(){
	int n;
	cin >> n;
	vector<int> a(n + 1), dp(n + 1);
	for(int i = 1; i <= n; i ++) cin >> a[i];
	dp[1] = a[1];
	int ma = a[1];
	for(int i = 2; i <= n; i ++){
		dp[i] = max(dp[i - 1] + a[i], a[i]);
		ma = max(ma, dp[i]);
	}
	cout << ma;
}

优化：可以边输入边处理，不需要额外开数组

void solve(){
	int n;
	cin >> n;
	ll sum = 0, ma = -1e18;
	for(int i = 1; i <= n; i ++){
		ll x;
		cin >> x;
		if(i == 1) sum = x;
		else{
			if(sum + x >= x) sum += x;
			else sum = x;
			ma = max(ma, sum);
		}
	}
	
	cout << ma << '\n';
}

C. Yarik and Array

思路：合格区间分段处理即可

void solve(){
	int n;
	cin >> n;
	vector<ll> a(n + 1);
	for(int i = 1; i <= n; i ++) cin >> a[i];
	ll l = 1, r = 2, ma = -1e18;
	while(l <= r && r <= n){
		if((a[r - 1] & 1) != (a[r] & 1)) r ++;
		else{
			ll sum = 0, mn = -1e18;
			for(int j = l; j < r; j ++){
				if(sum + a[j] >= a[j]) sum += a[j];
				else sum = a[j];
				mn = max(sum, mn);
			} 
			ma = max(ma, mn);
			l = r, r ++;
		}
	}
//	cout << l << ' ' << r << '\n';
	ll sum = 0, mn = -1e18;
	for(int j = l; j < r; j ++){
		if(sum + a[j] > a[j]) sum += a[j];
		else sum = a[j];
		mn = max(sum, mn);
	} 
	ma = max(ma, mn);	
	cout << ma << '\n';
}

也可以不用双指针可以更好的解决

void solve(){
	int n;
	cin >> n;
	vector<ll> a(n + 1), dp(n + 1);
	for(int i = 1; i <= n; i ++) cin >> a[i];
	dp[1] = a[1];
	ll ma = dp[1];
	for(int i = 2; i <= n; i ++){
		if(abs(a[i] - a[i - 1]) % 2 == 0) dp[i] = a[i];
		else dp[i] = max(dp[i - 1], 0ll) + a[i];
		ma = max(ma, dp[i]);
	}
	cout << ma << '\n';
}