#链家补测# 求元素个数为m,间隔大于等于k的最大子序列和。
由于没有提交上,也没有搜到类似的题目,所以不知道对不对。于是贴出自己的代码来讨论讨论。
dp[i][j]表示满足以下条件的所有子序列中,和的最大值:
1. 第一个数是A[i]
2. 包含j个数
#include <bits/stdc++.h> using namespace std; int max_sum(vector<int> &A, int n, int m, int k) { vector<vector<int>> dp(n, vector<int>(m + 1)); dp[n - 1][1] = A[n - 1]; for (int i = n - 2; i >= 0; --i) dp[i][1] = max(dp[i + 1][1], A[i]); int res = INT_MIN; for (int i = n - 1 - k; i >= 0; --i) { for (int j = 2; j <= (n - 1 - i) / k + 1; ++j) { dp[i][j] = dp[i + k][j - 1] + A[i]; res = max(res, dp[i][j]); } } return res; } int main() { int n = 0, m = 0, k = 0; cin >> n >> m >> k; vector<int> A(n); for (int i = 0; i < n; ++i) cin >> A[i]; int res = max_sum(A, n, m, k); cout << res << endl; }
-------------------------------------------------修改-------------------------------------------
dp[i][j]表示满足以下条件的所有子序列中,和的最大值:
1. 第一个数在A中的index大于等于i
2. 包含j个数
int max_sum(vector<int> &A, int n, int m, int k) { vector<vector<int>> dp(n, vector<int>(m + 1)); dp[n - 1][1] = A[n - 1]; for (int i = n - 2; i >= 0; --i) { dp[i][1] = max(dp[i + 1][1], A[i]); } int res = INT_MIN; for (int i = n - 1 - k; i >= 0; --i) { for (int j = 2; j <= (n - 1 - i) / k + 1; ++j) { dp[i][j] = max(dp[i + 1][j], A[i] + dp[i + k][j - 1]); } } return dp[0][m]; }
感谢@蜗牛.04 的回复。
#算法工程师#