1912. 연속합

 

 

1. 문제 분석
    1) N개의 정수로 이루어진 임의의 수열에서, 연속된 하나 이상의 수를 선택해서 "가장 큰 합"을 구한다.

2. 제약 조건
    1) 1 <= N <= 100000
    2) -1000 <= 주어지는 수 <= 1000

3. 의사결정
    1) 몇 개의 수를 선택할건지, 어디부터 어디까지 선택할건지에 따라 합이 달라진다. 모두 해봐야 할 듯?
    3) 각 수에 대해 누적합을 계산해나간다.
    4) 가장 큰 수만 하나 남긴다.

import java.io.*;

import java.util.*;

public class App {

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 가장 큰 수 초기화

        int maxNum = Integer.MIN_VALUE;

        // N 입력받기

        int N = Integer.parseInt(br.readLine());

        // 수 입력받기

        int[] input = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {

            int num = Integer.parseInt(st.nextToken());

            input[i] = num;

            // 개별 수 중에서 가장 큰 수 저장해두기

            if (maxNum < num) {

                maxNum = num;

            }

        }

        if (input.length == 1) {

            System.out.println(maxNum);

            return;

        }

        // 계산하기

        int hap = 0;

        int currentMax = 0;

       

        for (int i = 1; i < N; i++) {

            hap = Math.max(input[i], hap + input[i]);

            currentMax = Math.max(currentMax, hap);

        }

       

        System.out.println(currentMax);

    }

}