构成最大总和的数字

Question

构成最大总和的数字

3

我刚刚写了一个程序，可以从数组中找到最大的总和，但是我卡在了如何找出哪些数字对于最大总和做出了贡献？

给定最大总和的规则：不允许相邻元素对总和进行贡献。

我的解决方案最大总和问题：

public class MaximumELementInARray {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        String[] al = reader.nextLine().split(" ");
        int[] input = Arrays.stream(al).mapToInt(Integer::parseInt).toArray();
        MaximumELementInARray mm = new MaximumELementInARray();
        int maxi = mm.maximumm(input);
        System.out.println(maxi);
    }

    public int maximumm(int[] a) {
        List<Integer> ex = new ArrayList<>();
        List<Integer> inc = new ArrayList<>();
        int incl = a[0];
        int excl = 0;
        int excl_new;
        for (int i = 1; i < a.length; i++) {
            excl_new = Math.max(incl, excl);
            incl = excl + a[i];
            excl = excl_new;
        }
        System.out.println(incl > excl ? inc : ex);
        return incl > excl ? incl : excl;
    }
}

现在在maximum函数中，是否有一个调整的方法可以把构成最大总和的所有元素的索引放入一个数组中？

输入：

-1 7 8 -5 4 9 -2 3

输出：

20

**

我需要知道20是如何得到的。答案应该是8+9+3 **

我认为在maximum函数中我们可以放入一个ArrayList并记录哪些元素对总和做出了贡献，但我无法实现。

我已经建立了两个ArrayList：

List<Integer> ex = new ArrayList<>();
List<Integer> inc = new ArrayList<>();

输入：-1 7 8 -5 4 输出：12 这个总和是由8和4组成的

输入：3 2 1 -1 输出：4 这个总和是由3和1组成的

等等...

- tromu

1

先生，最大和的计算是基于这样一个规则：和中不应包含相邻的元素。 - tromu

你正在尝试解决一个寻找子集总和为给定数字的任务，这在一般情况下是NP完全问题，通常通过动态规划来解决。更好的解决方案将是修改MaximumELementInARray.maximum方法，不仅返回结果总和本身，还包括形成它的加数。 - Alex Salauyou

@AlexSalauyou，我很想知道解决方案和方法。 - tromu

要对项目进行“标记”，请操作索引，而不是项目本身。 - Alex Salauyou

@JoakimDanielson，我认为Java版本没有任何限制，只是我无法理解逻辑。 - tromu

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hadi J · Accepted Answer

你可以按照这段代码进行操作。

    int toIndex = 3, fromIndex = 0;
    List<Integer> result = new ArrayList<>();
    while (toIndex < numbers.size()) {
        Map<Integer, Integer> map = IntStream
                .range(fromIndex, toIndex)
                .filter(i->numbers.get(i)>0)
                .mapToObj(i -> new AbstractMap.SimpleEntry<>(i, numbers.get(i)))
                .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey,(a,b)->b));
        // find max of sublist
        int maxOfSub = numbers.subList(fromIndex, toIndex).stream().max(Integer::compareTo).get();
        //update indexes
        fromIndex = map.getOrDefault(maxOfSub,toIndex-1) + 2;
        toIndex += fromIndex;

        if (maxOfSub > 0)
            result.add(maxOfSub);
    }
    int lastMax = numbers.subList(fromIndex, numbers.size()).stream().max(Integer::compareTo).get();
    if (lastMax > 0)
        result.add(lastMax);
    System.out.println(result);
    System.out.println(result.stream().reduce(0, Integer::sum));

演示