Python에서 m으로 하위 배열 모듈로의 최대 합을 찾는 프로그램

<시간/>

n개의 요소가 있는 배열 num이 있다고 가정합니다. 또 다른 정수 m이 있습니다. 모듈로 m의 하위 배열 합계의 최대값을 찾아야 합니다.

따라서 입력이 nums =[1,5,7,3] m =5와 같으면 출력은

이기 때문에 3이 됩니다.

[1] 모드 5 =1
[5] 모드 5 =0
[7] 모드 5 =2
[3] 모드 5 =3
[1,5] 모드 5 =1
[5,7] 모드 5 =2
[7,3] 모드 5 =0
[1,5,7] 모드 5 =3
[5,7,3] 모드 5 =0
[1,5,7,3] 모드 5 =1

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

csum :=목록이고 처음에 nums[0] mod m을 여기에 삽입
첫 번째 값을 제외한 숫자의 각 x에 대해 수행
- csum 끝에 (csum + x의 마지막 항목) mod m 삽입
seen :=처음에 0인 단일 요소가 있는 목록
최대 합계 :=-1
csum의 각 s에 대해 다음을 수행합니다.
- idx :=목록이 정렬되도록 s를 삽입할 가장 왼쪽 위치
- idx <본 크기인 경우
  - max_sum :=max_sum 및 s의 최대값
- 그렇지 않으면
  - 배열이 정렬되도록 가장 왼쪽 인덱스에 s를 삽입합니다.
- 배열이 정렬되도록 가장 왼쪽 인덱스에 s를 삽입합니다.
최대값 반환

예시

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

import bisect
def solve(nums, m):
   csum = [nums[0] % m]
   for x in nums[1:]:
      csum.append((csum[-1] + x) % m)

   seen = [0]
   max_sum = -1
   for s in csum:
      idx = bisect.bisect_left(seen, s)
      if idx < len(seen):
         max_sum = max(max_sum, s, (s - seen[idx]) % m)
      else:
         max_sum = max(max_sum, s)
      bisect.insort_left(seen, s)

   return max_sum

nums = [1,5,7,3]
m = 5
print(solve(nums, m))

입력

"pptpp", [(1,1),(1,4),(1,1),(0,2)]