找到可被给定数整除的数组元素的最大和

Question

来自编程问题。

问题如下：

将给出一个数字数组以及我们必须除以的数字k。而且我们必须从该数组中选择元素，以使这些元素的总和可被k整除。这些元素的总和应尽可能大。

输入：

在第一行n上，表示元素数。

在下一行上给出n个数字。

在下一行，我们必须除以k。

输出：

通过从数组s.t.中选择元素来获得最大和。总和可被k整除。

样本输入：

5 
1 6 2 9 5
8

样本输出：

16

请注意，可以通过一个以上的数字组合获得16，但是这里我们只关心最大和。

我的建议解决方案：

我遍历数组，并为给定的输入数组在数组b中保持累积和：

b=[1 7 9 18 23]

并且将数组b中的数字乘以k，并将其存储到

c=[1 7 1 2 7]

现在c中具有相同值的数字，即索引0和索引2；索引1和索引4。现在我有了所有解决方案，答案将是

max(b[2]-b[0],b[4]-b[1])

并且在情况下，三个索引在c中具有相同的值，即在情况下

c=[1 2 3 1 1 2]

答案将是

max(b[4]-b[0],b[5]-b[1])

基本上用最右边的出现减去该数字的最左边的出现。

我的解决方案仅在存在contiguos元素时才有效。元素之和可被k整除。期待描述正确的解决方案]]

来自编程问题。问题如下：将给出一个数字数组以及我们必须除以的数字k。我们必须从该数组中选择元素，例如...

Answer 1

我相信您的解决方案是不正确的，因为您仅考虑连续数字。例如，如果输入为

Answer 2

听起来像subset sum的变体：您希望最大和的子集被k整除。

Answer 3

注：对于特殊情况，当数字为3时，很容易在O(n log n)时间找到答案。

Answer 4

import java.util.*;

public class MaxSumDivisible 
{

    static int max,divisor;

public static void main(String...okok)
{
    Scanner sc=new Scanner(System.in);
    String str=sc.nextLine();
    String ss[]=str.split(" ");
    LinkedList<Integer> list= new LinkedList<Integer>();
    for(int i=0;i<ss.length;i++)
    {
        list.add(Integer.parseInt(ss[i]));
    }
    divisor=sc.nextInt();
    FindMaxSum(list,0);
    System.out.println(max);
}
public static void FindMaxSum(LinkedList<Integer> list, int currentsum)
{
    if(currentsum%divisor==0 && currentsum>max)
    {
        max=currentsum;
    }

    for(int num:list)
    {
        LinkedList<Integer> li2= new LinkedList<Integer>(list);
        li2.remove(new Integer(num));
        FindMaxSum(li2,currentsum+num);

    }
}
}

Answer 5

以下代码专门针对给定的数字3。可以被3整除的数组元素的总和。您可以将其进一步推广。主要思想是为每个mod 3跟踪可能达到的最大总和]

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        dp[1] = dp[2] = Integer.MIN_VALUE;
        for(int x : nums) {
            int[] dpNext = new int[3];
            dpNext[0] = Math.max(dp[x%3] + x, dp[0]);
            dpNext[1] = Math.max(dp[(x+1)%3] + x,dp[1]);
            dpNext[2] = Math.max(dp[(x+2)%3] + x,dp[2]);
            dp = dpNext;
        }
        return dp[0];
    }
}