[JAVA] 백준 1912번 - 연속합

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int sum = 0;
		int ans = 0;
		int arr[] = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		for (int i = 0; i < N; i++) {
			sum += arr[i];
			if(sum < 0) sum = 0;
			ans = Math.max(ans, sum);
		}
		
		if(ans == 0) { // 모든 원소가 음수이므로
			Arrays.sort(arr);
			System.out.println(arr[arr.length-1]);
		}else {
			System.out.println(ans);
		}
		
	}
}

👨🏻‍💻 결과

배열의 원소 하나씩 더해가면서 합이 음수가 되면 0으로 초기화하고 다시 더해가면서 최댓값을 찾습니다.
만약 최댓값이 0이라면 배열의 모든 원소가 음수였다는 의미이므로 정렬을 하여 가장 큰 수를 출력해줍니다.

 

 

🔗 링크

https://www.acmicpc.net/problem/1912

1912번: 연속합