# 實作題 - 最大和 - APCS - by Peter Wang
## 題目資訊
此題為2016.10.29測驗中的題目2
###### tags: `APCS`

## 題目敘述
給定N群數字，每群都恰有M個正整數。若從每群數字中各選擇一個數字 (假設第 i群所選出數字為ti)，將所選出的N個數字加總即可得和 S = t1+t2+…+ +…+ tN。請寫程式計算 S的最大值 (最大總和 )，並判斷各群所選出的數字是否可以整除 S。

### 輸入：
第一行有二個正整數 N和 M， 1≦ N ≦ 20 ，1≦ M ≦ 20 。

接下來的N行，每一行各有M個正整數 xi ，代表一群整數，數字與數字間有一個空格，且 1≦ i ≦M，以及 1≦ xi ≦256 。

### 輸出：
第一行輸出最大總和 S。

第二行按照被選擇數字所屬群的順序，輸出可以整除S的被選擇數字，數字與數字間以一個空格隔開，最後一個數字後無空白；若 N個被選擇數字都不能整除S，就輸出 -1。

## 解題思路
開一個maxarr記住每群最大的數字，並加到total中，最後再判斷是否整除後輸出。

## 程式碼

#include<iostream>
#include<string.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int m;
        cin>>m;
        int arr[n][m];
        int maxarr[n];
        memset(maxarr,0,sizeof(maxarr));
        int total=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>arr[i][j];
                if(arr[i][j]>maxarr[i]){
                    maxarr[i]=arr[i][j];
                }
                else{
                    continue;
                }
            }
            total+=maxarr[i];
        }
        cout<<total<<endl;
        int x=0;
        for(int i=0;i<n;i++){
            if(total%maxarr[i]==0){
                cout<<maxarr[i]<<" ";
                x++;
            }
        }
        if(x==0){
            cout<<-1<<endl;
        }
        cout<<endl;
    }
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=c295)
[原題PDF檔](https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx6c2dpdGl0aXR8Z3g6NTRkNzUxYTBkMmNjYTZmOA)

## 備註
>[name=PeterWang]
>[time=Mon, Jun 14, 2021 12:02 AM]