[알고리즘] Java / 백준 / 연속합 / 1912

[알고리즘] Java / 백준 / 연속합 / 1912

문제

문제 링크

접근 방식

투 포인터로 연속 합이 양수일 때까지는 r을 올리면서 합을 더하고, 연속합이 음수가 될 때 l과 r을 r+1로 바꾸고 연속 합을 0으로 초기화 시킨다.

그 도중에 최댓값을 계속 갱신시켜준다.

코드

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

public class Main_1912 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int nums[] = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		int l = 0;
		int r = 0;
		int sum = 0;
		int max = -1001;
		
		while(r<n) {
			sum += nums[r];
			max = Math.max(max, sum);
			
			if(sum < 0) {
				l = r+1;
				r = l;
				if(l == n) break;
				sum = 0;
			}else {
				
				r++;
			}
			
			
		}
		max = Math.max(max, sum);
		System.out.println(max);
		
	}

}