#链家补测# 求元素个数为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 的回复。
#算法工程师#
全部评论
dp[i][j]=max(dp[i-1][j], dp[i-k][j-1] + a[i])
点赞 回复 分享
发布于 2017-08-22 09:39
做过间隔为2的😂大概思路是动态的时候跳过中间的间隔,其余的和没间隔的没差别
点赞 回复 分享
发布于 2017-08-21 21:46
为毛前端岗也是这个,做的心好累
点赞 回复 分享
发布于 2017-08-21 21:51
lintcode有到题叫 打劫房屋 差不多
点赞 回复 分享
发布于 2017-08-22 06:40
感觉要三重循环啊,因为任意位置的差
点赞 回复 分享
发布于 2017-08-22 09:46
import java.util.Scanner; public class Main { public static void main(String[] args) { // write your code here Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); int [] a = new int[n]; for(int i = 0; i<n; i++){ a[i] = sc.nextInt(); } System.out.println(langest(a,n,m,k)); } public static int langest(int [] a, int n, int m, int k){ int sum = 0; int max = 0; int nn = 0; for(int i = 0; i<n; i++){ nn = 0; for(int j = i+1; j<n; j++){ //for(int mm = i; mm<j; mm++){ if(j-i >= k && nn < m) { sum = a[i] + a[j]; nn = nn +2; } if(sum > max) max = sum; } //} } return max; } } 在IEDA平台测没问题,不知道是不是能覆盖所有测试用例
点赞 回复 分享
发布于 2017-08-22 10:15

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务