Codeforces Round 909 (Div. 3)

C. Yarik and Array

题意
求给定命组的连续子序列和的最大值，并且要求子序列中相邻元素奇偶性不同
思路
dp，与求数组最长递增子序列类似
dp表示以元素arr末了的符合条件的子序列的最大和，则递推公式为：dp = max(dp[i - 1] + arr, arr)

1. void solve()
2. {
3.     int n;
4.     cin >> n;
5.     vector<int> arr(n + 1);
6.     fer(i, 1, n + 1) cin >> arr[i];
8.     int *dp = new int[n + 2];
9.     dp[0] = 0;
10.     fer(i, 1, n + 1) dp[i] = arr[i];
12.     int ans = -1e9;
13.     fer(i, 1, n + 1)
14.     {
15.         if ((arr[i] + arr[i - 1]) & 1)
16.             dp[i] = max(dp[i - 1] + arr[i], arr[i]);
17.         ans = max(ans, dp[i]);
18.     }
19.     cout << ans << '\n';
20. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。