Суммы песочных часов с использованием Java 8 IntStream

Question

Я пытаюсь решить Максимальная сумма песочных часов в матрице :

При заданной двумерной матрице задача состоит в том, чтобы найти максимальную сумму песочных часов.

Часовой стакан состоит из 7 ячеек в следующем виде.

A B C
  D
E F G

Что-то не так с моей реализацией, и я получаю странные ответы.Я должен получить 19, но он возвращает 36.

Вот мой код:

static int hourglassSums(int[][] arr)
{
    return IntStream.range(0, 4).map(x -> {
        return IntStream.range(0, 4).map(y ->
                  arr[y][x] + arr[y][x + 1] + arr[y][x + 2] 
                  + arr[y + 1][x + 1] 
                  + arr[y + 2][x] + arr[y + 2][x + 1] + arr[y + 2][x + 2]
        ).sum();
    }).max().getAsInt();
}

public static void main(String[] args) 
{
    System.out.println("Max sum :: " + hourglassSums(new int[][] {
                    {1, 1, 1, 0, 0, 0},
                    {0, 1, 0, 0, 0, 0},
                    {1, 1, 1, 0, 0, 0},
                    {0, 0, 2, 4, 4, 0},
                    {0, 0, 0, 2, 0, 0},
                    {0, 0, 1, 2, 4, 0}
    }));
}

Answer 1

Вы уже вычисляете сумму каждого песочного часа внутри своего внутреннего map звонка.Поэтому ваша операция терминала sum(), примененная к внутреннему IntStream, не имеет смысла, поскольку она добавляет суммы нескольких часовых часов.

Ваш код фактически возвращает 38, что является суммой следующих часовых очков:

hour      hour
glass     glass
          sum

1 0 0
  0          2
1 0 0

0 0 0
  0         10
2 4 4

1 0 0        
  4          7
0 2 0

2 4 4 
  2         19
1 2 4
            --
            38

Вы можете исправить это, найдя максимальную сумму внутреннего IntStream, а затем максимальную сумму внешнего IntStream:

static int hourglassSums(int[][] arr) {
      return IntStream.range(0, 4).map(x -> {
          return IntStream.range(0, 4).map(y ->
                  arr[y][x] + arr[y][x + 1] + arr[y][x + 2] 
                  + arr[y + 1][x + 1] 
                  + arr[y + 2][x] + arr[y + 2][x + 1] + arr[y + 2][x + 2]
          ).max().getAsInt(); // find the max hour glass sum of all the hour
                              // glasses starting at column x
      }).max().getAsInt(); // find the overall max hour glass sum
}

Это приводит к

Max sum :: 19

Лучшей альтернативой будет использование flatMap:

static int hourglassSums(int[][] arr) {
      return IntStream.range(0, 4)
                      .flatMap(x -> IntStream.range(0, 4)
                                             .map(y -> arr[y][x] +
                                                       arr[y][x + 1] +
                                                       arr[y][x + 2] +
                                                       arr[y + 1][x + 1] +
                                                       arr[y + 2][x] +
                                                       arr[y + 2][x + 1] +
                                                       arr[y + 2][x + 2]))
                      .max()
                      .getAsInt();
}

Таким образом, вы создаете IntStream всех сумм песочных часов и находите максимальное значение этого потока.

Answer 2

Проблема в том, что вы выполняете итерацию 4 раза (0 - 3), но песочные часы должны быть только 3 числами в самом широком смысле.вам нужно повторить только 3 раза (0 - 2):

static int hourglassSums(int[][] arr) {
    return IntStream.range(0, 3).map(x -> {
        return IntStream.range(0, 3).map(y ->
                arr[y][x] + arr[y][x + 1] + arr[y][x + 2] 
                + arr[y + 1][x + 1] 
                + arr[y + 2][x] + arr[y + 2][x + 1] + arr[y + 2][x + 2]
        ).sum();
    }).max().getAsInt();
}

Вывод:

19

Который из песочных часов:

2, 4, 4, 
   2, 
1, 2, 4