각 셀 행렬[r, c]이 해당 셀에 있는 동전의 수를 나타내는 2D 행렬이 있다고 가정합니다. 행렬[r, c]에서 동전을 집어들면 행 (r - 1)과 (r + 1)의 모든 동전과 두 셀 행렬[r, c + 1]에 있는 동전이 사라집니다. 행렬[r, c - 1]. 모을 수 있는 최대 코인 수를 찾아야 합니다.
따라서 입력이 다음과 같으면
| 2 | 8 | 7 | 6 |
| 10 | 10 | 4 | 2 |
| 5 | 9 | 2 | 3 |
그러면 동전 8, 6, 9와 3이 있는 셀을 선택할 수 있으므로 출력은 26이므로 총합은 26이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- getmax() 함수를 정의합니다. 시간이 걸립니다
- prev_max :=0
- curr_max :=0
- res :=0
- arr의 각 숫자에 대해 다음을 수행합니다.
- temp :=curr_max
- curr_max :=num + prev_max
- prev_max :=temp 및 prev_max의 최대값
- res :=res 및 curr_max의 최대값
- 반환 결과
- 메인 방법에서 다음을 수행하십시오 -
- 행렬이 비어 있으면
- 0을 반환
- m :=행렬의 행 수
- n :=행렬의 열 개수
- row_sum :=크기가 m이고 0으로 채워진 배열
- 0 ~ m - 1 범위의 i에 대해
- row_sum[i] :=getmax(matrix[i])
- getmax(row_sum) 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def getmax(arr): prev_max, curr_max = 0, 0 res = 0 for num in arr: temp = curr_max curr_max = num + prev_max prev_max = max(temp, prev_max) res = max(res, curr_max) return res def solve(matrix): if not matrix: return 0 m, n = len(matrix), len(matrix[0]) row_sum = [0 for _ in range(m)] for i in range(m): row_sum[i] = getmax(matrix[i]) return getmax(row_sum) matrix = [ [2, 8, 7, 6], [10, 10, 4, 2], [5, 9, 2, 3] ] print(solve(matrix))
입력
[ [2, 8, 7, 6], [10, 10, 4, 2], [5, 9, 2, 3] ]
출력
26