2022.03.16 81일차

백준 1912번 (연속합)

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

나의 풀이

1. 음수를 기준으로 접근하기, 합(sum = 0)과 정답(answer = 0)을 변수로 두기
2. 음수전까지는 합을 구해놓기, 음수보다 합이 크면 그대로 진행시키기
3. 음수의 값이 더 크면 구해놓은 합과 정답 중 큰 값을 정답으로 변경, 합은 다시 0으로 변경
4. 모든 값이 음수인 경우 고려, 조건을 하나 설정하여 모든 값이 음수면 그 중 최대값(max)을 정답으로 변경

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int sum = 0;
        int answer = 0;

        boolean minus = true;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st.nextToken());
            max = Math.max(max, temp);

            if (temp < 0) {
                if (sum > Math.abs(temp)) {
                    sum += temp;
                }
                else {
                    answer = Math.max(answer, sum);
                    sum = 0;
                }
            }
            else {
                minus = false;
                sum += temp;
                answer = Math.max(answer, sum);
            }
        }

        if (minus) {
            answer = max;
        }

        System.out.println(answer);
    }
}

생각하기

• 복잡하게 접근
  양수 음수 구분없이 sum에 더한 후 최대값 비교 후 sum이 음수면 다시 0으로 변경

sum += Integer.parseInt(st.nextToken());
answer = Math.max(max, sum);
if (sum < 0) {
	sum = 0;
}