[알고리즘] 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);
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / 연속합 / 1912), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-연속합-1912저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)