Codeforces Round 909 (Div. 3)
C. Yarik and Array
题意
求给定数组的连续子序列和的最大值，并且要求子序列中相邻元素奇偶性不同
思路
dp，与求数组最长递增子序列类似
dp[i]表示以元素arr[i]结尾的符合条件的子序列的最大和，则递推公式为：dp[i] = max(dp[i - 1] + arr[i], arr[i])
void solve()
{
int n;
cin >> n;
vector<int> arr(n + 1);
fer(i, 1, n + 1) cin >> arr[i];
int *dp = new int[n + 2];
dp[0] = 0;
fer(i, 1, n + 1) dp[i] = arr[i];
int ans = -1e9;
fer(i, 1, n + 1)
{
if ((arr[i] + arr[i - 1]) & 1)
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}