[백준 코딩테스트] 1912번 연속합

풀이

처음에는 중첩 반복문을 사용해 sliding window 방식을 사용해 문제를 해결하려고 하니 자꾸만 시간 초과가 떴다.

	int size = 1;
        int answer = Integer.MIN_VALUE;

        while(size <= n){
            for(int j=0; j<=n-size; j++){
                int sum=0;
                for(int i=j; i<j+size; i++){
                    sum += input[i];
                }
                answer = Math.max(answer, sum);
            }
            size++;
        }

이렇게 되면 시간복잡도가 기하 급수적으로 증가해서 그런 것 이었다.
그래서 카데인 알고리즘을 적용해서 문제를 풀어보았다.
maxSoFar와 currentMax 변수를 배열의 첫번째 값으로 초기화하고 반복문을 사용해 최대 부분합을 구하였다.

int maxSoFar = input[0];
int currentMax = input[0];

for (int i = 1; i < n; i++) {
    currentMax = Math.max(input[i], currentMax + input[i]);
    maxSoFar = Math.max(maxSoFar, currentMax);
}

currentMax 변수를 사용해 현재 인덱스에서 부분 배열을 다시 시작할지, 이전 인덱스의 최대 부분합을 연장해 사용할 것인지 결정한다. currentMax + input[i]가 크다면 이전 인덱스의 최대 부분합을 연장해 사용하는 것이 낫다는 의미이다. 그리고 이렇게 currentMax 값이 갱신되면 자연스럽게 maxSoFar의 값도 갱신된다.

내 코드

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


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

        // 첫 번째 줄에서 n 읽기
        int n = Integer.parseInt(br.readLine());
        
        // 두 번째 줄에서 수열 읽기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] input = new int[n];

        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        // Kadane의 알고리즘 적용
        int maxSoFar = input[0];
        int currentMax = input[0];

        for (int i = 1; i < n; i++) {
            currentMax = Math.max(input[i], currentMax + input[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        System.out.println(maxSoFar);
    }
}