모래시계 문제

이 문제는 hackerrank에 대한 도전을 기반으로 합니다. 약간 까다로운 초보자 수준의 문제입니다.

문제는 주어진 2d 정수 배열에서 모든 모래시계 모양의 숫자 합계의 최대값을 찾는 것입니다.

6 x 6 배열(2d)이 제공됩니다.

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

그리고 아시다시피 모래시계 모양의 숫자가 있습니다.
첫 번째는 아래에 있습니다.

1 1 1
  1
1 1 1

이 모래시계의 합은 (1 + 1 + 1) + (1) + (1 + 1 + 1) = 7
7이 가장 큽니다.

이제 문제입니다. 아래의 2d 배열이 제공됩니다.

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

모래시계처럼 보이는 숫자의 최대 합을 찾아야 합니다.



여기에서 나는 모래 시계 모양의 숫자에 동그라미를 쳤습니다.

빨간색 모래시계의 합은
(-9 + -9 + -9) + (-9) + (-9 + -9 + -9) = -63



나머지 모래 시계 합계는 다음과 같습니다.

-63, -34, -9, 12, 
-10,   0, 28, 23, 
-27, -11, -2, 10, 
  9,  17, 25, 18

최대 모래시계는 다음과 같습니다. 합은 28이다.



그렇다면 모래시계처럼 보이는 숫자의 최대값은 어떻게 계산할까요?

다음 단계를 따라야 합니다.

배열의 각 인덱스를 반복합니다.

각 지역 모래시계의 모래시계 합계를 구합니다.

현재 합계가 이전 합계보다 높으면 최대 = 현재입니다.

최대값을 인쇄합니다.

첫 번째 행 첫 번째 열부터 시작하여 인덱스(0, 0)입니다. 아래 모래시계가 들어 있습니다.

-9 -9 -9
   -9
-9 -9 -9

따라서 다른 중첩 루프를 사용하여 이 모래시계의 합을 찾아야 합니다.

그런 다음 두 번째 모래시계는 (0, 1)의 인덱스에 있습니다. 아래 모래시계가 들어 있습니다.

-9 -9  1
-9  0  4
-9 -9  1

합계는 이 두 번째 항목에서도 계산됩니다.

두 번째가 첫 번째보다 높으면 최대값을 두 번째 합계로 할당할 수 있습니다. 이것은 끝날 때까지 반복됩니다.

그러나 (0, 4) 인덱스와 그 이후의 인덱스에서 모래시계 모양의 숫자를 만들 수 없기 때문에 마지막 요소까지 갈 필요가 없습니다.

또한 행 방향의 경우 모래시계가 이후에 형성되지 않기 때문에 (4, 0) 인덱스로 이동하는 것은 유효하지 않습니다.

아래 링크를 사용하여 소스 코드 찾기

https://github.com/lizardkingLK/hourglass_problem