[SWEA] 5642 합

출처: SWEA

 Input 

1

5

1 3 -8 18 -8

 

 Output 

#1 18

 

모든 원소가 음수인 경우 주의해야 한다.

 Input 

1

5

-5 -4 -3 -2 -1

 

 Output 

#1 -1

 

※ 유사문제 풀이:  [BOJ] 1912 연속합 

[BOJ] 백준 1912 연속합

---

#include <iostream>
using namespace std;
int arr[100000];
#define MIN -1001
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int testCase; cin >> testCase;
    for (int tc = 1; tc <= testCase; ++tc) {
        int N; cin >> N;
 
 
        int answer = MIN;
        for(int i=0; i<N; ++i){
            cin >> arr[i];
            // 원소 중 최대값 찾기
            answer = answer < arr[i] ? arr[i] : answer;
        }
        // 모든 원소가 음수인 경우
        // 원소 1개가 부분합의 최대값에 해당
        if(answer <= 0){
            printf("#%d %d\n", tc, answer);
            continue;
        }
 
 
        // 원소 중 양수가 있는 경우
        int partialSum = 0;
        for(int i=0; i<N; ++i){
            partialSum += arr[i];
            // 부분합이 음수가 된다면 0으로 처리
            if(partialSum < 0) partialSum = 0;
            // 기존 최대값과 비교
            answer = answer < partialSum ? partialSum : answer;
        }
            
        // 정답 출력
        printf("#%d %d\n", tc, answer);
    }
}