首页 > 试题广场 >

组合幸运数字

[编程题]组合幸运数字
  • 热度指数：1244 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小易的幸运数字是7，现有一个整数数组 nums，请你找出并返回能被七整除的子集合的最大和，如果找不到则返回-1。

输入描述:
一个正整数数组列表nums，用空格区分，1<=length(nums)<=100000，sum(nums) <= 1000000000


输出描述:
一个整数，最大和
示例1

输入

7 3 1 4

输出

14

说明

7+3+4
示例2

输入

6 5

输出

-1

说明

找不到 一个子数组，和能被7整除
示例3

输入

10 20 2 29

输出

49

说明

20+29
算法知识视频讲解
添加回答
JavaScript
一只小塔姆头像 一只小塔姆

这道题很难, 一开始会想到遍历得到所有的子集合的和, 但是却不知道如何遍历得到。因为这里的子集合长度可以为1 ~ nums.length，一般的遍历无法满足！

举例： 1 2 3 4

一般的遍历是 1， 1 2， 1 2 3， 1 2 3 4， 2， 2 3， 2 3 4， 3，3 4，4实现这个遍历已经是O(n^2)的复杂度了! 可是这还没结束, 还需要 1 3, 1 3 4, 1 4, 2 4, 这种循环遍历极其难写出来!!

🌟那我们这里想到了一个巧妙地方法, 逆向思维, 由于全部的数之和sum肯定是由所有的数组成, 那我们可以试着慢慢地扒元素下来直到把所有元素扒完,

比如说我们这里有一个数组 [a,b,c,d], 依次扒开就很容易得到所有的组合 
const readline=require('readline');
const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
});
/*
 小易的幸运数字是7，现有一个整数数组 nums，
 请你找出并返回能被七整除的子集合的最大和，如果找不到则返回-1
 输入:
 一个正整数数组列表nums，用空格区分，1<=length(nums)<=100000，sum(nums) <= 1000000000
 */
rl.on('line',function (line) {
    /*1.处理数据*/
    let arr=line.trim().split(' ').map(Number);

    /*2.dp*/
    //由于是全是正整数,所以 sum >= arr.length
    let sum=arr.reduce((a,b)=>a+b);
    //dp[i]记录i是否能够得到 1为可得到,0则相反
    let dp=new Array(sum+1).fill(0);
    dp[0]=1; dp[sum]=1;
    /*这个方法很巧妙, 最初是a+b+c+d,每次从所有的满足条件的子集合减去一个数
    * 这样就很方便的得到了所有的排列*/
    for (let i=0;i<arr.length;i++){
        for (let j=0;j<=sum;j++){
            if (dp[j]===1&&j>=arr[i]){
                dp[j-arr[i]]=1;
            }
        }
    }

    let maxSum=-1;
    for (let i=dp.length-1;i>=7;i--){
        if (dp[i]===1&& i%7===0){
            maxSum=i;
            break;
        }
    }
    console.log(maxSum);
})


编辑于 2021-03-27 22:13:33 回复(1)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 网易 游戏研发工程师 2021 大数据开发工程师
上传者：小小
难度：
1条回答 5600浏览

热门推荐

通过挑战的用户

相关试题

组合幸运数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号