코드트리 [자바 java] 연속 부분 합의 최댓값 구하기 2

https://www.codetree.ai/missions/8/problems/max-of-partial-sum-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

배열 안에서 연속한 구간 중 구간 내 수들의 합의 최댓값을 구하는 문제이다.

 

여기서는 그리디 알고리즘을 사용하였다.

 

<연속 부분합의 최댓값 구하기>

 

어떤 배열이 주어지고, 해당 배열속의 특정 구간의 합 중 가장 큰 값을 구하라는 문제가 있다고 가정합시다.

 이 문제에서 그리디를 사용하는 방법은 왼쪽 끝부터 차례로 구간을 확장시키면서 옆으로 나아가다가 합이 음수가 되면 멈추고 새로운 구간을 만드는 것입니다.

 위와 같은 경우에는 -5를 만난 직후 SUM이 음수가 됩니다. 이 때 여기서 3을 더하면 -2가 되지만, 새로운 구간을 3에서부터 시작한다면 SUM이 3이 됩니다(음수를 더하면 무조건 총합이 작아진다). 이로 인해 이제까지의 구간의 합이 음수라면 다음 INDEX부터 새로운 구간을 시작하는 것이 무조건 더 큰 합을 만들 수 있다는 것을 알 수 있습니다.

 

위의 개념을 사용하였다.

 

이 때 주의할 점이 모든 수가 음수일 경우이다.

 

 for(int i = 0;i<n;i++){
            if(sum + arr[i] < 0) sum = 0;
            else sum += arr[i];

            max = Math.max(sum,max);
        }

 

원래는 위와 같이 풀었었는데 틀렸습니다가 나왔다. 

틀린 이유는 모든 수가 음수일 경우 최댓값이 0이 나오기 때문이었다. 이를 보완하기 위해서 우선 sum에 해당 수를 더한 다음, max여부를 판단하고, 만약 sum이 음수이면 0으로 바꿔주는 코드를 사용했다.

 

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

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[] arr = new int[n];

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

        int sum = 0;

        int max = -10000000;

        for(int i = 0;i<n;i++){
            sum += arr[i];
            max = Math.max(sum,max);
            if(sum < 0) sum = 0;
        }

        System.out.println(max);


    }
}