Причина этой ошибки в том, что у вас есть дубликат <key> при вызове Stream.collect().Помните, этот метод выполняет изменяемую операцию сокращения над элементами потока.Поэтому, когда ваш вызов:
.collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));
Здесь вы определяете <keys> объекта Map как <values> из Entry<index, values>, определенного методом Stream.mapToObj().Теперь, когда в вашем тесте данных у вас есть 4, 5, 4, 3, это означает, что вы пытаетесь создать <key> для числа 4 дважды.Следовательно, вы получили это IllegalStateException.
Но как я могу это исправить?
Очень просто, просто измените определение вашего объекта Map с <values, indexes> на <indexes, values> вStream.collect() вызов. Как я могу это сделать? Ну, просто замените Map.Entry::getValue на Map.Entry::getKey и наоборот, как здесь:
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
Кроме того, есть лучший эквивалент с использованием IntStream.boxed() метод.Этот метод возвращает Stream, состоящий из элементов этого потока, каждый из которых упакован в Integer.Для меня это лучший способ преобразовать объект List в объект Map, например:
Map<Integer, Integer> map = IntStream
.range(fromIndex, toIndex)
.boxed()
.collect(Collectors.toMap(i -> i, i -> numbers.get(i) > 0 ? numbers.get(i) : 0));
Обратите внимание, что я использую это выражение i -> numbers.get(i) > 0 ? numbers.get(i) : 0 для присвоения <values> изMap объект. Зачем вы это делаете? Потому что нам нужно отследить удаление отрицательных чисел, чтобы я заменил их на ноль.Метод Stream.filter() является альтернативой, но объект Map не будет содержать отфильтрованных элементов.
Однако это изменение повлияет на то, как вы обновляете свои индексы, потому что теперь значения карты равны <values>, а не <indexes>, как показано в этой строке:
fromIndex = map.getOrDefault(maxOfSub, toIndex - 1) + 2;
Toисправить это вам просто нужно конвертировать, получите <index> от corespondent <value> следующим образом:
fromIndex = IntStream
.range(fromIndex, toIndex)
.filter(i -> map.get(i).equals(maxOfSub))
.findFirst()
.orElse(toIndex - 1) + 2;
Альтернативное решение
Теперь, приведенная выше информация будет решать только IllegalStateException.Однако я обнаружил, что есть еще одна ошибка.Если я использую этот массив чисел 1, 9, 1, 7, 7, 5, 4, 1, 6, максимальная сумма несмежных чисел должна быть [9 + 7 + 5 + 6] = 27, но ваш код получил [9 + 7 + 6] = 22.Поэтому я попытался найти решение для этого здесь:
public class Ideone
{
public static void main(String[] args)
{
// List<Integer> numbers = Arrays.asList(4, 5, 4, 3);
// List<Integer> numbers = Arrays.asList(1, 9, 1, 7, 7, 5, 4, 1, 6);
List<Integer> numbers = Arrays.asList(-1, 7, 8, -5, 4, 9, -2, 3);
String sss = "";
String ddd = "";
Ideone mm = new Ideone();
List<List<Integer>> maxi = mm.findMaxSumNonAdjacentStream(numbers, numbers.size());
System.out.println(Collections.singletonList(maxi));
}
public List<List<Integer>> findMaxSumNonAdjacentStream(List<Integer> numbers, int size)
{
int fromIndex = 0;
Map<Integer, Integer> maxSumMap = IntStream
.range(fromIndex, size)
.boxed()
.collect(Collectors.toMap(i -> i, i -> numbers.get(i) > 0 ? numbers.get(i) : 0));
Map<Integer, List<Integer>> indexMap = IntStream
.range(fromIndex, size)
.mapToObj(i -> new AbstractMap.SimpleEntry<>(i, Collections.singletonList(numbers.get(i))))
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
maxSumMap.replace(1, Math.max(numbers.get(1), numbers.get(0)));
List<Integer> maxValList = maxSumMap
.entrySet()
.stream()
.filter(entry -> entry.getKey() > 1)
.map(entry -> {
int index = entry.getKey();
int prevOne = index - 1;
int prevTwo = index - 2;
int prevValOne = maxSumMap.getOrDefault(prevOne, 0);
int prevValTwo = maxSumMap.getOrDefault(prevTwo, 0);
int maxVal = Math.max(prevValOne, prevValTwo + entry.getValue());
boolean exclude = prevValOne > (prevValTwo + entry.getValue());
List<Integer> elements = new ArrayList<>();
if (prevValOne > 0 && exclude) {
elements = new ArrayList<>(indexMap.get(prevOne));
} else if (prevValTwo > 0 && !exclude) {
elements = new ArrayList<>(indexMap.get(prevTwo));
}
if (!exclude) {
elements.add(entry.getValue());
elements = elements.stream().sorted(Integer::compareTo).collect(Collectors.toList());
}
maxSumMap.replace(index, maxVal);
indexMap.replace(index, elements);
return index;
})
.collect(Collectors.toList());
Integer max = maxValList
.stream()
.mapToInt(v -> v)
.max().orElseThrow(NoSuchElementException::new);
int lastMax = maxValList.stream().max(Integer::compareTo).orElse(-1);
Integer maxVal = maxSumMap.get(max);
List<Integer> result = maxSumMap
.entrySet()
.stream()
.filter(entry -> entry.getValue().equals(maxVal))
.map(i -> i.getKey())
.collect(Collectors.toList());
Predicate<Map.Entry<Integer, List<Integer>>> containMaxList =
mapEntry -> result.contains(mapEntry.getKey());
return indexMap.entrySet()
.stream()
.filter(containMaxList)
.map(i -> i.getValue())
.collect(Collectors.toList());
}
}