BOJ) 연속합

연속합

1912번: 연속합

풀이

오늘 어려운 문제에 여러개 도전하다가 실패해서 그런지 머리가 잘 돌아가지 않았다.

그래서, 예전에 풀었던 기억이 있어서 참고해서 풀었다.

우선, 막혔던 부분은 partialSum을 저장하는 부분이었다.

Math.max(0,partialSum)을 통해 해당 번호에서 다시 시작하는게 좋은지, 지금까지 더해왔던 수를 계속 이용하는게 좋은지 판별해주는 부분이 놓친 부분이었다.

 

이전까지의 합이 양수면, 거기에 더해주는게 더 합리적이기 때문에..

또한, 0과 비교하는 이유는, 이전의 합이 음수면 -1이든 -99999든 이전까지 부분 합을 지워주고, 새롭게 출발하는게 더 좋기 때문이다.

 

이외에는 크게 어려운 부분은 없다.

 

부분합을 구하면서 max를 최신화 시켜주면, 쉽게 답을 찾을 수 있다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int total = Integer.parseInt(br.readLine());
        String inputStr = br.readLine();
        br.close();

        System.out.println(solution(total,inputStr));
    }

    private static int solution(int total, String inputStr) {

        StringTokenizer st = new StringTokenizer(inputStr);
        int max = Integer.parseInt(st.nextToken());
        int partialSum =max;

        for(int i=1; i<total; i++) {
            int num = Integer.parseInt(st.nextToken());
            partialSum = Math.max(0, partialSum) + num;
            max = Math.max(max, partialSum);
        }

        return max;
    }
}