1912. 연속합

- 시간복잡도를 계산할 때, 왼쪽부터 오른쪽으로 한번의 순환으로 구해야만 한다.

- 왼쪽부터 순서대로 더할 때, 양수일 경우는 무조건 합의 덧셈의 영향을 주므로 계속해서 더해가고, 음수일 경우는 앞으로 나아가는 방향에서 덧셈에 영향보다는 뺄셈의 영향을 주므로 그 때는 다시 연속합의 덧셈을 진행하기 위해 sum의 인자를 0으로 초기화 한다.

- 모든 계산에서 최댓값의 변수인 maxValue와 현재 연속합의 sum의 변수를 비교해 최댓값을 계속해서 갱신해 나아간다.

package december.fifth;

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

public class B_1912_연속합 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int maxValue = Integer.MIN_VALUE;
		int sum = 0;
		for (int i = 0; i < N; i++) {
			sum += arr[i];
			maxValue = Math.max(maxValue, sum);
			if (sum < 0)
				sum = 0;
		}
		System.out.println(maxValue);
	}
}