回溯法

package test;

import java.util.*;
/*
给你一个整数类型的数组，要求你每次取一个数字，但你取完这个数字后，这个数字左边和右边的数字不允许去取，输出你能取到的数字累加起来总数最大的值。

如：
输入：[2,5,3,4]
输出：9
解释：先拿5，2和3不允许拿，然后拿4，累加起来最大的总数为5 + 4 = 9。
给你一个整数类型的数组，要求你每次取一个数字，但你取完这个数字后，这个数字左边和右边的数字不允许去取，输出你能取到的数字累加起来总数最大的值。

如：
输入：[2,5,3,4]
输出：9
输入：[2,5,3,4,9,13,25,1]
输出：39
解释：先拿5，2和3不允许拿，然后拿4，累加起来最大的总数为5 + 4 = 9。
 */
public class BackTrackTest {

    public static void main(String[] args) {
        Scanner s  = new Scanner(System.in);
        String input = s.nextLine();

        String[] chars = input.split(",");

        Set<Integer> maxSet = new TreeSet<Integer>();

        List<Integer> result = new LinkedList<>();

        backTrack(0,chars,result,maxSet);


        System.out.println(maxSet.stream().max(Integer::compareTo));
    }

    public static void backTrack(int i, String[] chars, List<Integer> result,Set<Integer>maxSet){

        int max = 0;

        if(i>chars.length-1){
            Iterator<Integer> iterator = result.iterator();
            while (iterator.hasNext()){
                max+=iterator.next();
            }
            maxSet.add(max);

        }else {

            result.add(Integer.valueOf(chars[i]));
            backTrack(i+2,chars,result,maxSet);
            result.remove(result.size()-1);
            backTrack(i+1,chars,result,maxSet);


        }




    }
}