C++의 최대 하위 배열 합계 모듈로 m

이 문제에서 크기 n과 정수 m의 배열이 제공됩니다. 우리의 임무는 C++에서 최대 부분배열 합 모듈로 m을 찾는 프로그램을 만드는 것입니다.

프로그램 설명 − 여기서, subarray의 모든 요소의 합을 m으로 나눈 최대값을 구합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={4, 9,2} m =6

출력 - 5

설명 − 모든 부분배열과 나누기의 나머지 부분

<이전>{4}:4%6 =4{9}:9%6 =3{2}:2%6 =2{4, 9}:13%6 =1{9, 2}:11%6 =5{4, 9, 2}:15%6 =3

이 문제를 해결하기 위해 prefixSumModulo Array를 계산합니다. 그리고 수식을 사용하여 각 인덱스의 maxSum을 계산합니다. maxSum at i =(prefixi + prefixj + m)%m

예시

우리의 솔루션을 설명하는 프로그램,

#include네임스페이스 사용 std;int calcMaxSum(int arr[], int n, int m) { int x, prefix =0, maxSumMod =0; 집합 합계; 합계.삽입(0); for (int i =0; i  출력
 최대 하위 배열 합계 모듈로 5는 4입니다.