我剛剛編寫(xiě)了程序,該程序從數(shù)組中找到最大和,
但我陷入困境,有什么辦法可以找到哪些數(shù)字促成了最高金額？

Rule of Maximum sum is given: No adjacent elements should contribute
to sum.

我對(duì)數(shù)組中最大和的解決方案：

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;
    }
}

現(xiàn)在在最大函數(shù)中有一個(gè)調(diào)整,可以將構(gòu)成最大和的所有元素索引放到哪里？

輸入：

-1 7 8 -5 4 9 -2 3

輸出：

20

**

我需要20點(diǎn)到達(dá).答案應(yīng)該是8 9 3

**

我相信在最大功能中,我們可以放置一個(gè)Arraylist并記錄哪些元素對(duì)總和起作用,但我無(wú)法實(shí)現(xiàn).

我做了兩個(gè)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組成

等等….

解決方法:

您可以遵循此代碼.

    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));

DEMO