#链家补测# 求元素个数为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 的回复。
#算法工程师#
