从数组中选出和为 7 的倍数的子序列的最大和

Tag: 笔试算法题 Posted on 2022-03-27 12:09:12 Edited on 2022-03-27 12:09:12 Views: 185

概述

从数组中选出和为 7 的倍数的子序列的最大和

回溯法

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;
int ans = 0;

void backtrack(int i, int sum) {
    if (i == nums.size()) {
        if (sum % 7 == 0) {
            ans = max(ans, sum);
        }
        return;
    }
    backtrack(i + 1, sum + nums[i]);
    backtrack(i + 1, sum);
}

int main() {
    int n; cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    backtrack(0, 0);
    cout << ans << endl;
}

分治法

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;

set<int> helper(int i, int j) {
    set<int> res;
    if (i == j) {
        res.insert(0);
        res.insert(nums[i]);
        return res;
    }
    int m = (i + j) / 2;
    auto s1 = helper(i, m);
    auto s2 = helper(m + 1, j);
    for (auto a : s1) {
        for (auto b : s2) {
            res.insert(a + b);
        }
    }
    return res;
}

int main() {
    int n; cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    auto s = helper(0, n - 1);
    int ans = 0;
    for (auto a : s) {
        if (a % 7 == 0) {
            ans = max(ans, a);
        }
    }
    cout << ans << endl;
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/