[백준-누적합] 1912 연속합

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

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

1912번: 연속합

---

풀이

나의 풀이

- 연속되는 합의 값이 현재 수 값보다 낮은 경우, 더 이상 가치가 없는 수라고 판단했다.

- 연속되는 합의 값이 현재 수 값보다 높은 경우에만 누적합을 진행하여 저장한 뒤, 저장한 값 중 제일 큰 값을 반환하였다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(bf.readLine());

        int[] prefix = new int[n+1];
        int temp;
        int answer = -1000000001;

        st = new StringTokenizer(bf.readLine());
        for(int i=0; i<n; i++) {
            temp = Integer.parseInt(st.nextToken());
            prefix[i+1] = Math.max(prefix[i] + temp, temp);
            answer = Math.max(answer, prefix[i + 1]);
        }

        System.out.printf("%d", answer);
    }
}