An algorithm to find 'Independent Set of Maximum Weight' (solution to Exercise 6.1(c) from the first edition of Algorithm Design by Jon Kleinberg, Eva Tardos.) in Java, part of Algorithm Design and Analysis course.

IndependentSetOfMaximumWeight.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class IndependentSetOfMaximumWeight {
    public static void main(String[] args) {
        System.out.println("Independent set of maximum weight: " 
                + findIndependentSetOfMaximumWeight(Arrays.asList(6, 8, 7, 6, 8, 1)));
    }

    private static int getWeight(List<Integer> list) {
        return list.stream().mapToInt(Integer::intValue).sum();
    }

    private static List<Integer> findIndependentSetOfMaximumWeight(List<Integer> originalGraph) {
        if (originalGraph.size() <= 1) {
            return new ArrayList<>(originalGraph);
        }

        List<Integer> graph = new ArrayList<>(originalGraph);
        graph.add(0, 0);
        graph.add(0, 0);

        List<List<Integer>> sets = new ArrayList<>();
        sets.add(new ArrayList<>());
        sets.add(new ArrayList<>());
        sets.add(new ArrayList<>(Collections.singletonList(graph.get(2))));

        for (int i = 3; i < graph.size(); i++) {
            List<Integer> set = new ArrayList<>();
            if (getWeight(sets.get(i - 3)) + graph.get(i) > getWeight(sets.get(i - 2)) + graph.get(i)) {
                set.addAll(sets.get(i - 3));
            } else {
                set.addAll(sets.get(i - 2));
            }
            set.add(graph.get(i));
            sets.add(set);
        }

        if (getWeight(sets.get(sets.size() - 1)) > getWeight(sets.get(sets.size() - 2))) {
            return sets.get(sets.size() - 1);
        } else {
            return sets.get(sets.size() - 2);
        }
    }
}

can you explain to me how do you create the graph?

FYI, this gist basically is a solution to Exercise 6.1(c) from the first edition of Algorithm Design by Jon Kleinberg, Eva Tardos.