[Algorithm] Maximise Sum

Maximise Sum

---

[Problem]

배열의 크기를 나타내는 N과 다른 정수 M이 주어진다. 

(부분합 % M)의 최대값을 구하라.

[Input Format]

[Output Format]

[Constraints]

2<= N <=10^5

1<= M <= 10^14

[Solve]

import java.io.*;

import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static int max = 0;
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        Scanner scanner = new Scanner(System.in);
        
        int T = scanner.nextInt();
        
        for(int i=0; i<T; i++){
            
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            
            int[] arr = new int[N];
            for(int idx=0; idx<N; idx++){
                arr[idx] = scanner.nextInt();
            }
            
            pick(arr, 0, 1, N, M);
            System.out.println(max);
            max=0;
        }// end total cases
        
    }// end main 
    
    public static void pick(int[] arr, int startIdx, int eleCnt, int N, int M){
        
        // end condition
        if(eleCnt == N)
            return ;
        if(startIdx==N-1){
            pick(arr, 0, eleCnt+1, N, M);   
        }
        
        if(startIdx+eleCnt < N){
            calMax(arr, startIdx, eleCnt, N, M);
            pick(arr, startIdx+1, eleCnt, N, M);
        }
        else if(startIdx+eleCnt == N){
            calMax(arr, startIdx, eleCnt, N, M);
            pick(arr, 0, eleCnt+1, N, M);
        }
        else{
            pick(arr, 0, eleCnt+1, N, M);
        }
        
    }// end pick()
    
    public static void calMax(int[] arr, int startIdx, int eleCnt, int N, int M){
        int tmpSum = 0;
            // calculate subArr sum % M 
            for(int i=0; i<eleCnt; i++){
                tmpSum += arr[startIdx+i]; 
            }
            if(max < (tmpSum % M))
                max = tmpSum % M;
    }
}