파이썬에서 합이 최대 k인 직사각형의 합을 찾는 프로그램

<시간/>

2차원 행렬과 또 다른 값 k가 있다고 가정하면 sum ≤ k인 사각형의 가장 큰 합을 찾아야 합니다.

따라서 입력이 다음과 같으면

5	−2
7	10

k =15이면 출력은 12가 됩니다. 직사각형 [5, 7]을 사용하여 12의 합이 15보다 작기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=
의 행 수
m :=a
의 열 개수
ans :=inf
범위 0에서 n의 i1에 대해 수행
- row :=크기가 m이고 0으로 채워진 목록
- 범위 i1에서 n까지의 i2에 대해 수행
  - 0에서 m 사이의 j에 대해 수행
    - 행[j] :=행[j] + a[i2, j]
  - s :=새로운 세트
  - s에 0 삽입
  - 합계 :=0
  - 0에서 m 사이의 j에 대해 수행
    - 합계 :=합계 + 행[j];
    - temp :=(sum - k)보다 큰 s의 모든 항목에 대한 목록
    - 임시 크기> 0이면
      - u :=최소 온도
      - ans :=ans의 최대값 및 (sum - u)
    - 합계를 s에 삽입
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, a, k):
      n = len(a)
      if n == 0:
         return 0;
      m = len(a[0])
      ans = -999999;
      for i1 in range(n):
         row = [0]*m;
         for i2 in range(i1, n):
            for j in range(m):
               row[j] += a[i2][j]
            s = set()
            s.add(0)
            sum = 0
            for j in range(m):
               sum += row[j];
               temp = [e for e in s if e > (sum − k)]
            if len(temp) > 0:
               u = min(temp)
               ans = max(ans, sum − u)
            s.add(sum)
         return ans
ob = Solution()
matrix = [
   [5, −2],
   [7, 10]
]
k = 15
print(ob.solve(matrix, k))

입력

[
[5, −2],
[7, 10]
], 15